Comment juger s’il y a même des 1 dans la représentation binary d’un nombre en utilisant C?

Il y a déjà des questions sur le calcul du nombre de 1 dans un nombre, mais cette question consiste à déterminer s’il existe un nombre pair ou impair de 1.

Toute instruction en boucle ou conditionnelle (y compris le commutateur) n’est pas autorisée. De même, les opérateurs de division, de multiplication ou de module doivent être évités. Pour être plus précis, nous pouvons supposer qu’il s’agit d’un entier non signé de 32 bits.

En fait, j’ai déjà une implémentation, mais je ne peux pas comprendre pourquoi cela fonctionne. Toute preuve de son exactitude ou toute nouvelle idée serait très utile.

 int even_ones(unsigned x) { x ^= x>>16; x ^= x>>8; x ^= x>>4; x ^= x>>2; x ^= x>>1; return !(x & 1); } 

Je suppose que vous savez ce que l’opération exclusive ou ^ fait – si deux bits ont la même valeur, le résultat est 0 – sinon, il s’agit de 1 . Ainsi, lorsque j’ai deux nombres d’un bit, A et B, alors A^B sera égal à zéro si A et B sont tous deux égaux à 0 ou 1 . En d’autres termes – la sum de ceux dans A et B est même …

Faisons maintenant ceci deux bits à la fois: C et D sont des nombres à deux bits. Voici les combinaisons possibles:

 CDC^D 00 00 00 even 01 00 01 odd 10 00 10 odd 11 00 11 even 00 01 01 odd 01 01 00 even 10 01 11 even 11 01 10 odd 00 10 10 odd 01 10 11 even 10 10 00 even 11 10 01 odd 00 11 11 even 01 11 10 odd 10 11 01 odd 11 11 00 even 

Comme vous pouvez le constater, l’opération dans chaque instance réduit le nombre de bits de moitié et le nombre résultant de 1 bits est impair si vous démarrez avec un nombre impair (car des paires de 1 s s’annulent, mais toutes les autres sont inchangé).

Maintenant, il devrait être évident de voir pourquoi la même chose continue à être vraie quand vous commencez avec des nombres plus grands (4 bits, 8 bits, 16 bits). Essentiellement, votre algorithme commence par un nombre de 32 bits et le divise en deux nombres de 16 bits. En éliminant les “doubles 1”, le nombre de bits est réduit de moitié; agit ensuite sur la moitié restante et le répète jusqu’à ce qu’il ne rest qu’un seul bit. En vérifiant si ce bit est un (impair) ou zéro (pair), vous obtenez votre réponse.

Au cas où ce ne serait pas clair, une opération comme x ^= x>>16 décale en fait les 16 bits supérieurs dans les 16 bits inférieurs et génère un OU exclusif à cet endroit. En réalité, il ne supprime pas les éléments les plus importants, donc “un désordre est laissé pour compte”. Mais l’algorithme ignore ce désordre dans ce qui suit. Voir ce qui suit (en commençant par 8 bits pour plus de simplicité):

 x = abcdefgh x >> 4 = 0000abcd new x = abcdijkl x >> 2 = 00abcdij new x = abmnopqr x >> 1 = 0abmnopq new x = astuvwxy 

En cela, le dernier chiffre y est le XOR de r et q , qui sont à leur tour les XOR de l,j et k,i ; ceux-ci sont à leur tour les XOR de h,d , f,b , g,c et e,a respectivement. Comme vous pouvez le voir, vous avez fini avec le XOR de tous les bits; et comme je l’ai expliqué ci-dessus, cela signifie soit “tous les pairs”, soit “tous les impairs”, selon que le bit le moins significatif est maintenant un 1 ou un 0 .

J’espère que cela a aidé.

Voici plusieurs variantes permettant de calculer rapidement la parité d’un octet ou d’un mot. La méthode la plus rapide dépend de votre processeur et de la rapidité des opérations de base. Par conséquent, s’il s’agit en quelque sorte du goulot d’étranglement de votre application, vous devez profiler chacune d’entre elles pour déterminer celle qui fonctionne le mieux sur votre ordinateur cible.

Votre solution est très similaire à l’implémentation “Calculer la parité en parallèle” , sans l’optimisation intelligente à la fin. Ce qui se passe ici, c’est qu’à chaque étape, vous exécutez la moitié des bits avec l’autre moitié jusqu’à ce qu’il ne vous rest plus qu’un bit. La parité d’un mot est 0 s’il existe un nombre pair de 1 et 1 s’il existe un nombre impair de 1; ou de manière équivalente, la parité d’un mot est simplement le XOR de tous les bits du mot.

Comme l’opérateur XOR est commutatif et associatif, nous pouvons réorganiser la façon dont tous les bits du mot sont XOR ensemble. Ainsi, au lieu de calculer le XOR de tous les bits en XORing individuellement dans le résultat, nous xorons la moitié supérieure des bits avec la moitié inférieure des bits, réduisant ainsi de moitié le nombre de bits qui nous intéressent; quand il rest un peu, nous avons fini.

Notez que ce XOR est le plus significatif 16 bits avec le moins significatif 16 bits:

 x ^= x>>16; 

Ensuite, la série continue avec XOR-ing le 2ème bit le moins significatif avec le moins significatif 4 bits, notez que le plus significatif 16 bits est maintenant tout simplement une ordure, peu importe ce qui se passe, vous pouvez l’ignorer:

 x ^= x>>8; 

Et ainsi de suite, nous continuons à XOR-ing le deuxième bit le moins significatif avec le bit le moins significatif jusqu’à ce que nous arrivions à 1 bit; à ce jour, tous les bits sauf le bit le moins significatif sont indésirables, et la dernière ligne utilise simplement bit à bit et avec 1 pour obtenir le bit le moins significatif et l’inverser pour le test d’égalité.

Peut-être, il est plus facile de suivre si vous écrivez de cette façon:

 int even_ones(unsigned x) { a = (x ^ x>>16) & 0x0000FFFF; b = (a ^ a>>8) & 0x000000FF; c = (b ^ b>>4) & 0x0000000F; d = (c ^ c>>2) & 0x00000003; e = (d ^ d>>1) & 0x00000001; return !(e&1); } 

Pourquoi ça marche? Parce que XOR équivaut à une addition au bit sans retenue.

J’espère que cela t’aides ::

  enum { EVEN, ODD } even_odd; unsigned int check_even_odd_no_of_ones(unsigned int num) { if(num_of_ones(num) & 1) return ODD; else return EVEN; } 

Je vous remercie