décomposition binaire

Version imprimable

Bonjour,

Je cherche à créer une décomposition binaire d'un nombre décimal. Facile me direz-vous ! Mais mon programme bug pour des grands nombres > 2^31-1. Je ne suis pas du tout à l'aise avec les bits, donc merci de détailler vos réponses.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 // Calcul du nombre de chiffres qui forment n en binaire int taille (int n) { int i=0; if (!n) return 1; while (n) { i++; n/=2; } return i; } // Décomposition binaire de n renvoyée dans un tableau monodimensionnel int * decomposition (int n) { int *tab; int i; int tmp=n; tab=(int *) malloc(taille(n)*sizeof(int)); for (i=0; i<=taille(tmp)-1; i++) { tab[i]=n&1; n>>=1; } return tab; }

18/02/2006, 17h36
diogene

Citation:

Je cherche à créer une décomposition binaire d'un nombre décimal

D'un nombre, tout simplement

Citation:

bug pour des grands nombres > 2^31-1

Probablement que tes int sont codés sur 4 octets. Dans ce cas, la plus grande valeur codable est 2^31-1 et la plus petite -2^31. Si tu utilise des unsigned int tu peux coder de 0 à 2^32-1
18/02/2006, 17h39
babar56

Citation:

Envoyé par diogene

Citation:

Je cherche à créer une décomposition binaire d'un nombre décimal

D'un nombre, tout simplement

Ben non, il n'existe pas que les bases 2 et 10 donc c'est important que je le précise.

Et si je voulais entrer des nombres supérieurs à 2^32-1 de quelle façon faudrait-il modifier l'algorithme ?
18/02/2006, 18h00
reggae

Tu pourrais utiliser les long double qui sont codés sur 10 octets.
18/02/2006, 18h02
Emmanuel Delahaye

Citation:

Envoyé par babar56

Citation:

Envoyé par diogene

Citation:

Je cherche à créer une décomposition binaire d'un nombre décimal

D'un nombre, tout simplement

Ben non, il n'existe pas que les bases 2 et 10 donc c'est important que je le précise.

La représentation internes des nombres entiers est toujours binaire en C. Il n'y a pas de format interne BCD.

Citation:

Et si je voulais entrer des nombres supérieurs à 2^32-1 de quelle façon faudrait-il modifier l'algorithme ?

Il faut des entiers plus grands. Si tu as C99, tu peux utiliser long long qui garantit 64 bits.
18/02/2006, 18h08
diogene

Citation:

Je cherche à créer une décomposition binaire d'un nombre décimal

Citation:

D'un nombre, tout simplement

Ben non, il n'existe pas que les bases 2 et 10 donc c'est important que je le précise.

Ce que je veux dire, c'est que de toute façon tu travailles sur un nombre codé en mémoire.

Code:

int * decomposition (int n)

Il importe peu que ce nombre n ai été entré à partir d'une écriture dans une base donnée. D'ailleurs, ton code ne fait pas intervenir la base d'origine utilisée pour l'écriture de ce nombre.

Code:

Et si je voulais entrer des nombres supérieurs à 2^32-1

Peut être que les long sont plus grands sur ta machine
18/02/2006, 19h45
babar56

Citation:

Il importe peu que ce nombre n ai été entré à partir d'une écriture dans une base donnée. D'ailleurs, ton code ne fait pas intervenir la base d'origine utilisée pour l'écriture de ce nombre.

Justement, le code ne fait pas intervenir la supposition que l'utilisateur entre un nombre en base 10. J'aurais pu vouloir entrer de l'octal ou de l'hexa pour le convertir en binaire ... Donc je précise dans les hypothèses que j'entre du décimal. Si t'as pas envie d'admettre que t'as tord je peux le concevoir, par contre arrête de percister je trouve ça ridicule :)

Je vais essayer de voir ce que ça donne avec unsigned et long, mais il n'existe vraiment pas d'autres méthodes ?

Citation:

Envoyé par babar56

Citation:

Il importe peu que ce nombre n ai été entré à partir d'une écriture dans une base donnée. D'ailleurs, ton code ne fait pas intervenir la base d'origine utilisée pour l'écriture de ce nombre.

Justement, le code ne fait pas intervenir la supposition que l'utilisateur entre un nombre en base 10. J'aurais pu vouloir entrer de l'octal ou de l'hexa pour le convertir en binaire ...

Ce que tu dis n'a aucun sens. Tu confonds la représentation textuelle et la représentation interne.

Ce que tu saisies sur la ligne de commande (ou d'un fichier texte), c'est du texte et là, ca peut être effectivement en n'importe quelle base (strto[u]l() sait convertir à partir d'une représentation textuelle de 2 à 36).

Mais en langage C, une fois convertie en valeur numérique, cette valeur est stockée exclusivement en binaire.

Citation:

Donc je précise dans les hypothèses que j'entre du décimal. Si t'as pas envie d'admettre que t'as tord je peux le concevoir, par contre arrête de persister je trouve ça ridicule :)

Le paramètre de la fonction est un entier et non une chaine. Il serait temps de réouvrir un livre d'informatique avant de dire que les autres sont des ânes. Pour le moment, c'est toi qui mélange tout. Point.

Pour t'en convaincre :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <stdio.h> #include <stdlib.h> int main (void) { unsigned x = 0x80; unsigned y = 128; unsigned z = (unsigned) strtoul ("10000000", NULL, 2); /* affichage en decimal */ printf ("dec: x = %u y = %u z = %u\n", x, y, z); /* affichage en hexadecimal */ printf ("hex: x = %X y = %X z = %X\n", x, y, z); return 0; }
Ce qui donne
Code:

1 2 3 dec: x = 128 y = 128 z = 128 hex: x = 80 y = 80 z = 80
Citation:

Je vais essayer de voir ce que ça donne avec unsigned et long, mais il n'existe vraiment pas d'autres méthodes ?

Pour obtenir un entier > 32 bit, je ne connais que 'long long' ou 'unsigned long long' (C99).

18/02/2006, 20h19
babar56

On ne se comprend pas Emmanuel. Pardonne moi mais je t'ai lu en diagonale je n'ai pas vraiment le temps de chercher à comprendre ce que tu as voulu dire.

Ce programme de décomposition binaire décompose un entier entré en base 10, en base 2. Si j'entre 123 à mon programme je ne lui précise pas qu'il est en base 10, ça pourra très bien être un nombre en base 4 (=27 en décimal), 5 (=38 en décimal), 6 7 8 ou 9. Auquel cas le programme ne renvoie pas du tout la bonne décomposition binaire, l'algorithme n'étant pas prévu à cet effet. Je fais une supposition forte, celle de n'utiliser que des nombres en base 10. Et comme on est pas des animaux, je ne vais pas me contenter de vous laisser lire mon code pour comprendre ce que fais le programme, je vous l'écris, ça mange pas de pain. Compris ?
18/02/2006, 20h28
Anomaly

Change de ton s'il te plaît. Si tu ne veux pas lire les réponses, à quoi bon poster dans un forum ?

Ton problème est tout simple, il a déjà été dit plusieurs fois dans ce thread : tu utilises le type "int" pour stocker le résultat, et ce type ne peut pas mémoriser des nombres supérieurs à 2^31-1 dans ton cas. Solution : changer de type, long long ou long double, ou gérer les entiers sous forme de chaînes de caractères et écrire soi-même toutes les primitives (bon courage).
18/02/2006, 23h35
diogene

Citation:

Si t'as pas envie d'admettre que t'as tord je peux le concevoir, par contre arrête de percister je trouve ça ridicule

8O 8O 8O Quelle agressivité hors de propos !
Admettre que je me trompe (ce qui n'est pas le cas) ne me pose pas de problèmes philosophiques particuliers. Je ne persisterai pas à vouloir expliquer qq chose à celui qui s'offusque de l'aide qu'on essaye de lui apporter : je n'ai pas non plus une vocation sacrificielle.
Pour moi donc, ce sujet est clos et je passe le relais sans regrets à qui veut le prendre en lui souhaitant bon courage compte tenu de l'accueil qu'ils peuvent attendre.

Sans rancune , je te souhaite bonne chance pour la suite
19/02/2006, 13h07
babar56

En prenant des unsigned int je peux monter jusqu'à 4294967295=2^32-1.

long int ou long long int ne changent rien, le programme affiche un truc aberrant pour des nombre >2^31.

Vous n'avez pas d'idée pour une décomposition binaire d'un nombre plus grand ?!
19/02/2006, 13h56
Skyounet

Sous windows :
unsigned __int64
19/02/2006, 14h08
Emmanuel Delahaye

Citation:

Envoyé par babar56

En prenant des unsigned int je peux monter jusqu'à 4294967295=2^32-1.

C'est possible.

Citation:

long int ou long long int ne changent rien, le programme affiche un truc aberrant pour des nombre >2^31.

Quelle est ta plateforme ? (Machine, Système, Compilateur)
19/02/2006, 15h04
babar56

En ce moment je fais mes tests sur un athlon 64 sous windows xp avec dev c++. Mais cette fonction fait parti d'un projet plus gros qui devra tourner sous linux (mandriva il me semble) avec gcc.
19/02/2006, 15h12
Emmanuel Delahaye
Citation:

Envoyé par babar56

En ce moment je fais mes tests sur un athlon 64 sous windows xp avec dev c++. Mais cette fonction fait parti d'un projet plus gros qui devra tourner sous linux (mandriva il me semble) avec gcc.

Alors tant que tu es sous windows, la bibliothèque C est celle de Windows (MSVCRT.DLL) et elle n'est pas compatible C99. Il est donc normal que, même si ton compilateur supporte C99, la bibliothèque ne reconnaisse pas le formatteurs "%lld" et "%llu" de print(), mais sous Linux, ça fonctionnera.

Comme déjà suggéré, sous Windows, il faut utiliser le format propriétaire

__int64 ou unsigned __int64 et le formatteur "%I64d" ou "%I64u". Détails sur le forum "Développement Windows".
Code:

1 2 3 4 5 6 7 8 9 #include <stdio.h> int main (void) { printf ("%I64X\n", 1LLU << 63); return 0; }
Sortie :
Code:

1 2 8000000000000000
19/02/2006, 17h41
loufoque

Citation:

// Calcul du nombre de chiffres qui forment n en binaire

partie entière du log en base 2 + 1.
Ça marche aussi pour toutes les autres bases.

À part ça, un long long fait toujours au moins 64 bits, c'est dans la norme C99.
Donc un long long (signé) peut aller jusqu'à 2^63-1
19/02/2006, 19h49
Skyounet

Citation:

Envoyé par loufoque

Donc un long long (signé) peut aller jusqu'à 2^63-1

Si c'est 64 bits, il peut aller jusqu'a 2^64-1
19/02/2006, 21h56
Médinoc

Le fait de ne pas supporter %llu est un inconvénient du printf de microsoft, mais il a au moins l'avantage de supporter un format pour les nombres "32bits en mode 32bits, 64bits en mode 64bits"--> Les pointeurs et surtout les size_t, qui eux ne peuvent pas être affichés avec %p.

Où que j'aie cherché, je n'ai rien trouvé dans les formats standard...
19/02/2006, 22h01
Emmanuel Delahaye

Citation:

Envoyé par Médinoc

Les pointeurs et surtout les size_t, qui eux ne peuvent pas être affichés avec %p.

Où que j'aie cherché, je n'ai rien trouvé dans les formats standard...

:?: Les pointeurs peuvent être affichés avec "%p" et le cast (void*).
Pour size_t, c'est "%zu" en C99, mais en C90, on peut utiliser "%lu" et le cast (unsigned long).
19/02/2006, 22h07
Médinoc

Citation:

Envoyé par Emmanuel Delahaye

:?: Les pointeurs peuvent être affichés avec "%p" et le cast (void*).

Pardon, je rajoute les parenthèses:

Citation:

Envoyé par Médinoc

Les pointeurs et (surtout les size_t, qui eux ne peuvent pas être affichés avec %p).

:)

Citation:

Pour size_t, c'est "%zu" en C99, mais en C90, on peut utiliser "%lu" et le cast (unsigned long).

Ah, merci (au passage, pour ceux qui programment sous Windows, il faut utiliser "%Iu").
20/02/2006, 02h12
loufoque

Citation:

Envoyé par Skyrunner

Citation:

Envoyé par loufoque

Donc un long long (signé) peut aller jusqu'à 2^63-1

Si c'est 64 bits, il peut aller jusqu'a 2^64-1

Relis ce que j'ai écrit et remarque le "(signé)".