Bit de parité du code pour un nombre impair de bits

Je suis en train d'essayer de trouver la parité d'un bitstring de sorte qu'elle retourne 1 si x est impair # de 0.
Je ne peux utiliser de base opérations au niveau du bit et de ce que j'ai à ce jour passe la plupart des tests, mais je me demande 2 choses:

  1. Pourquoi x ^ (x + ~1)? Je suis tombé sur ceci, mais il semble vous donner 1 si il y a un nombre impair de bits et d'autre chose si même. Comme 7^6 = 1, car 7 = 0b0111
  2. Est-ce la bonne direction de résolution de problème pour cela? Je suppose que mon problème est issue de la première opération, en particulier (x + ~1) parce qu'il serait de dépassement de certaines complément de 2 numéros. Grâce

Code:

int bitParity(int x) {
    int first = x ^ (x + ~1);
    int second = first ^ 1; //if first XOR gave 1 you'll return 0 here
    int result = !!second;
return result;
}
Où avez-vous trouvé cet algorithme?
n'utilisez pas de int, il y aura débordement et ensuite, c'est un comportement indéfini. Utilisation unsigned et 1u au lieu de cela, voici l'écharpe autour de est bien défini.
Cet algorithme ne fonctionne pas. Elle renvoie 1 pour toutes les valeurs entre 0 et 255.
J'ai pris impair de bits des nombres binaires et XOR d, ET d, et un OU logique avec eux-mêmes moins 1 et XOR a été le seul qui a donné quelque chose d'utile (ou alors j'ai pensé).
Double Possible de bitParity - Trouver un nombre impair de bits en un nombre entier

OriginalL'auteur tippenein | 2011-09-23

  1. 3

    Je voudrais utiliser réelle de comptage plutôt que de niveau des bits hacks, qui profitent de la représentation des nombres, qui permettrait à la fois de se sentir plus sûr et plus propre et facile à comprendre. Probablement plus lent, bien sûr, mais c'est un bon compromis, surtout quand on ne sait rien sur les attentes en matière de rendement.

    Faire pour cela, il suffit d'écrire le code pour compter le nombre de bits à 1, la plus simple solution en général se résume à une boucle.

    Mise à JOUR: compte tenu de l' (bizarre et ennuyeux) limitations, ma réponse serait probablement détendez-vous la boucle donnée dans le "naïfs" solution sur le bithacks page. Ce ne serait pas joli, mais alors je pourrais aller faire quelque chose d'utile. 🙂

    Je n'aurais certainement utiliser une boucle pour facile de compter chaque bit ou même juste XOR de tous les morceaux ensemble, mais pour cette mission, je ne suis pas autorisé à utiliser les structures de contrôle. Juste | ^ & >> << ~ + ! Donc, votre réponse a été ma réaction, mais pas de dés.
    J'ai pris un code déjà écrit pour bit de comptage et juste ET d le résultat avec 0x1 pour voir si il y a un nombre impair de bits ou pas. Cependant, j'ai fait la bitCount(int x) algorithme par force brute; vérifié chaque bit avec !!(x & (1<<bit#)) Ce n'est pas assez bon pour moi pour le moment, mais le bit de parité problème a été résolu par la ce pour l'instant.

    OriginalL'auteur unwind

  2. 4

    Votre fonction de parité ne fait pas travailler autant que je puisse en dire -, il semble pour obtenir le droit de réponse à propos de la moitié du temps, qui est à peu près aussi bon que de retourner un résultat aléatoire (ou même simplement de renvoyer 0 ou 1 tout le temps).

    Il y a plusieurs niveau de bits de hacks qui ne fait le travail à: http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - vous aurez probablement envie de regarder le dernier de ces: http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel

    Je me rends compte que mon code ne fonctionne pas, mais le x ^ (x-1) semble donner des réponses qui fait sens pour les valeurs que j'ai essayé. Si vous êtes correct, alors je devrais simplement le jeter et recommencer.
    Juste essayer de la saisie de valeurs 0, 1, 2 et 3 et vous verrez qu'il n'est pas d'aller travailler.

    OriginalL'auteur Paul R

  3. 1

    Bits de parité peut être fait comme ceci:

    #include <stdio.h>

int parity(unsigned int x) {
    int parity=0;
    while (x > 0) {
       parity = (parity + (x & 1)) % 2;
       x >>= 1;
    }
}

int main(int argc, char *argv[]) {
    unsigned int i;
    for (i = 0; i < 256; i++) {
        printf("%d\t%s\n", i, parity(i)?"odd":"even");
    }
}

    OriginalL'auteur sastanin