Código de paridad de bits para el número impar de bits

Question

Estoy tratando de encontrar la paridad de una cadena de bits para que devuelva 1 si x tiene un número impar de 0.
sólo puedo utilizar las operaciones básicas de bits, por lo que tengo hasta ahora pasa la mayor parte de las pruebas, pero me pregunto 2 cosas:

1. ¿Por qué x^(x + ~ 1) el trabajo? Me encontré con esto, pero parece darte 1 si hay un número impar de bits y otra cosa si es par. Al igual que 7^6 = 1 porque 7 = 0b0111

2. ¿Es esta la dirección correcta de resolución de problemas para esto? Supongo que mi problema proviene de la primera operación, específicamente (x + ~ 1) porque desborda ciertos números de complemento de 2. Gracias

Código:

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; 
} 

Answer 1

me gustaría utilizar el conteo real en lugar de cortes a nivel de bits que se aprovechan de la representación de los números, que sería tanto se siente más seguro y sea más limpio y fácil de entender. Probablemente más lento, por supuesto, pero eso es una buena compensación, especialmente cuando uno no sabe nada sobre las expectativas de rendimiento.

Haga esto, solo escriba el código para contar el número de 1 bits, la solución más directa generalmente se reduce a un bucle.

ACTUALIZACIÓN: Dadas las limitaciones (extrañas y molestas), mi respuesta sería probablemente a unwind el bucle dada en la solución "naive" en la página bithacks. Eso no sería lindo, pero podría hacer algo útil. :)

Answer 2

Su función de paridad en realidad no funciona tan lejos como puedo decir - parece obtener la respuesta correcta la mitad del tiempo, que es casi tan buena como devolver un resultado aleatorio (o incluso simplemente devolver 0 o 1 todo el tiempo).

Hay varios cortes a nivel de bits que do trabajan realmente en: http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - es probable que desea buscar en el pasado uno de estos: http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel

Answer 3

bit de paridad se puede hacer así:

#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"); 
    } 
}