décomposition binaire

**babar56** · 18/02/2006, 15h39

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

**diogene** · 18/02/2006, 17h36

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

D'un nombre, tout simplement

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

**babar56** · 18/02/2006, 17h39

Envoyé par diogene

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 ?

**reggae** · 18/02/2006, 18h00

Tu pourrais utiliser les long double qui sont codés sur 10 octets.

**Emmanuel Delahaye** · 18/02/2006, 18h02

Envoyé par babar56

Envoyé par diogene

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.

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.

**diogene** · 18/02/2006, 18h08

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.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Peut être que les long sont plus grands sur ta machine

**babar56** · 18/02/2006, 19h45

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 ?

**Emmanuel Delahaye** · 18/02/2006, 20h03

Envoyé par babar56

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.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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).

**babar56** · 18/02/2006, 20h19

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 ?

**Anomaly** · 18/02/2006, 20h28

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).

**diogene** · 18/02/2006, 23h35

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

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

**babar56** · 19/02/2006, 13h07

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 ?!

**Skyounet** · 19/02/2006, 13h56

Sous windows :
unsigned __int64

**Emmanuel Delahaye** · 19/02/2006, 14h08

Envoyé par babar56

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

C'est possible.

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)

**babar56** · 19/02/2006, 15h04

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.

**Emmanuel Delahaye** · 19/02/2006, 15h12

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Sortie :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
8000000000000000

**loufoque** · 19/02/2006, 17h41

// 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

**Skyounet** · 19/02/2006, 19h49

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

**Médinoc** · 19/02/2006, 21h56

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...

**Emmanuel Delahaye** · 19/02/2006, 22h01

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).

décomposition binaire

C

Vue hybride

Discussions similaires

Partager

Partager