Comment savoir si un nombre binaire est divisé par 3 ?

Question

Je veux savoir s'il existe une règle de division dans le système binaire pour diviser par 3.

Par exemple : en décimal, si la somme des chiffres est divisée par 3, alors le nombre est divisé par 3. Par exemple : 15 -> 1+5 = 6 -> 6 est divisé par 3, donc 15 est divisé par 3.

La chose importante à comprendre est que je ne cherche pas un CODE qui le fera bool flag = (i%3==0) ; n'est pas la réponse que je cherche. Je cherche quelque chose qui est facile pour l'homme à faire tout comme la loi décimale.

Answer 1

Référez-vous à ce site web : Comment savoir si un nombre binaire est divisible par trois ?

En fait, il faut compter le nombre de bits de positions impaires non nulles et de bits de positions paires non nulles. de la droite . Si leur différence est divisible par 3, alors le nombre est divisible par 3.

Par exemple :

15 = 1111 qui a 2 bits impairs et 2 bits pairs non nuls. La différence est de 0. Ainsi 15 est divisible par 3 .

185 = 10111001 qui a 2 bits impairs non nuls et 3 bits pairs non nuls. La différence est de 1. Ainsi 185 n'est pas divisible par 3 .

Explication

Considérez le 2^n valeurs. Nous savons que 2^0 = 1 est congruente 1 mod 3 . Así, 2^1 = 2 est congénère 2*1 = 2 mod 3. En poursuivant le schéma, on remarque que pour 2^n où n est impair, 2^n est congruente 1 mod 3 et pour pair, il est congruent 2 mod 3 qui est -1 mod 3 . Así, 10111001 est congruente 1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3 qui est congruent 1 mod 3 . Ainsi, 185 n'est pas divisible par 3.