bitParity – Recherche d’un nombre impair de bits dans un entier

Je dois créer une fonction bitParity(int x) qui prend un entier et retourne 1 s’il existe un nombre impair de 0 sous la forme binary de x et 0 sinon.

Ex: bitParity(5) = 0, bitParity(7) = 1

Cependant, cela est difficile car je ne peux utiliser que des opérateurs de bits sur ce problème ( ! ˜ & ˆ | + <> sont les seuls légaux). Cela signifie, pas de boucles, if-then , ou quoi que ce soit de la sorte. Les constantes peuvent être utilisées.

Jusqu’à présent, ce que j’ai n’a pas fonctionné, mais je me suis dit que je devrais décaler les bits de l’entier 16 , 8 et 4 fois et XOR les entiers restants.

Quelqu’un peut-il offrir des conseils? Merci.

    Ceci est correctement résolu avec une boucle. Mais voici une façon de le faire sans.

     x = (x & 0x0000FFFF) ^ (x >> 16) x = (x & 0x000000FF) ^ (x >> 8) x = (x & 0x0000000F) ^ (x >> 4) x = (x & 0x00000003) ^ (x >> 2) x = (x & 0x00000001) ^ (x >> 1) 

    Edit: Je n’ai pas besoin du &. Une meilleure version:

     x ^= x >> 16 x ^= x >> 8 x ^= x >> 4 x ^= x >> 2 x ^= x >> 1 x &= 1; 

    Pour les numéros 32 bits:

     function bitParity(int x) { x ^= x >> 16; x ^= x >> 8; x ^= x >> 4; x &= 0xf; return (0x6996 >> x) & 1; } 

    Voici l’une de mes fonctions que j’ai utilisées lors de mon travail sur la thèse de licence;)

     /** Calculates number of bits in unsigned char * @brief Bit count * @param input to be checked * @return int 0-8 */ int bitCount( unsigned char input) { static unsigned char count[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; return (int)( count[ input & 0x0f] + count[ (input >> 4) & 0x0f] ); } 

    Donc, le nombre total pour le nombre entier 4B serait:

     int bytes = bitCount( (unsigned char)((number >> 0)&255)) + bitCount( (unsigned char)((number >> 8)&255)) + bitCount( (unsigned char)((number >> 16)&255)) + bitCount( (unsigned char)((number >> 24)&255)); 

    Et parité:

      return bytes%2; return bytes&1; // if you preffer 

    J’ai toujours voulu réutiliser ces codes 🙂

    EDIT : Comme vous pouvez le constater, le caractère unsigned char (8b) peut être divisé en 2 morceaux de 4b de long, ce qui signifie 16 valeurs faciles à stocker et à réutiliser. Donc, vous prenez les 8b premiers d’un entier, divisez-les en deux. Assurez-vous qu’ils sont tous les deux dans l’intervalle <0,15> et obtenez directement le nombre de bits. Répéter 🙂

    Voici ma réponse:

     int bitParity(unsigned x) { unsigned flag = 0; while (x != 0) { flag ^= (x & 1); x >>= 1; } return flag; } 

    edit: c’est faux, désolé je n’ai pas remarqué “pas de boucles, si-alors, ou quoi que ce soit de la sorte.”