Discussion :

[kojima]

salut
j'ai un exercice que je ne comprends meme pas
j'ai cherché sur google j'ai trouvé des solutions mais j'ai rien saisie
le probleme est le suivant
ecrire un algorithme permet de calculer le nombre de 0 dans la representation binaire de n
merci

[kojima]

je penses que j´ai compris l´algo
j´ai un nombre en binaire et j´affiche le nombre de zero qu´il y´a dans ce nombre
mais comment faire la

[droggo]

Ah,

Tu comptes les 1 dans la valeur = nUn, le nombre de 0 est longueur_en_bits_de_la_valeur - nUn !!

Plus sérieux : il suffit de tester un à un les bits de ta valeur

[pseudocode]

Si un nombre est pair, il se termine par un 0 en base 2.

Donc pour ton algo, tu divises successivement ton nombre par 2. A chaque fois que ca tombe juste -> un 0 de plus en base 2.

exemple: le nombre 12

12 / 2 = 6 --> 1er zero
6 / 2 = 3 --> 2eme zero
3 / 2 = 1 + 0.5
1 / 2 = 0 +0.5
0

Donc 2 zéros, ce qu'on peut verifier:

12 (base10) = 1100 (base2)

[kojima]

le nombre entré est deja en binaire

[pseudocode]

le nombre entré est deja en binaire

!!

[droggo]

Hol,

Soyons fous. Si la valeur a 32 bits de long, tu peux connaître le nombre de bits à 1 avec

donc, si pour ton compilateur int est codé sur 32 bits

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
typedef unsigned uint_32;
 
uint_32 countOneBits(uint_32 v)
// compte le nombre de bits à 1
{
    uint_32 w = v - ((v >> 1) & 0x55555555);                    // temp
    uint_32 x = (w & 0x33333333) + ((w >> 2) & 0x33333333);     // temp
    uint_32 c = ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
    return c;
}

Il faut passer en unsigned à cause des décalages.

C'est facilement adaptable à d'autres tailles pour la valeur