Даже четность unsigned int

Question

/*A value has even parity if it has an even number of 1 bits. 
*A value has an odd parity if it has an odd number of 1 bits. 
*For example, 0110 has even parity, and 1110 has odd parity. 
*Return 1 iff x has even parity. 
*/ 

int has_even_parity(unsigned int x) { 

} 

Я не уверен, с чего начать писать эту функцию, я думаю, что я прохожу через значение в виде массива и применяю к ним операции xor. Что-то вроде следующей работы? Если нет, каков способ приблизиться к этому?

int has_even_parity(unsigned int x) { 
    int i, result = x[0]; 
    for (i = 0; i < 3; i++){ 
     result = result^x[i + 1]; 
    } 
    if (result == 0){ 
     return 1; 
    } 
    else{ 
     return 0; 
    } 
} 

Answer 1

Вы не можете получить доступ к целому числу, как массив,

unsigned x = ...; 
// x[0]; doesn't work 

Но вы можете использовать битовые операции.

unsigned x = ...; 
int n = ...; 
int bit = (x >> n) & 1u; // Extract bit n, where bit 0 is the LSB 

Существует умный способ сделать это, предполагая, что 32-битные целые числа:

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

Answer 2

Option # 1 - итерация бит в "очевидном" способе, на O (число бит):

int has_even_parity(unsigned int x) 
{ 
    int p = 1; 
    while (x) 
    { 
     p ^= x&1; 
     x >>= 1; // at each iteration, we shift the input one bit to the right 
    } 
    return p; 

Вариант № 2 - итерацию только биты, которые установлены в 1, в точке о (количество 1s):

int has_even_parity(unsigned int x) 
{ 
    int p = 1; 
    while (x) 
    { 
     p ^= 1; 
     x &= x-1; // at each iteration, we set the least significant 1 to 0 
    } 
    return p; 
} 

Вариант № 3 - использовать алгоритм Swar для подсчета 1s, на O (log (количество битов)):

http://aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count%29