Четная четность беззнакового целого числа

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

c parity bits
person user2917692    schedule 05.02.2014    source источник
comment
См. здесь: stackoverflow.com/questions/109023/   -  person Linuxios    schedule 06.02.2014
comment
См. здесь: stackoverflow.com/questions /21617970/как-проверить-если-значение-имеет-четность-четность-бит-или-нечетно.   -  person Troyseph    schedule 27.10.2015

Ответы (2)


arrow_upward
3
arrow_downward

Вариант 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, при O(количество единиц):

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 для подсчета единиц при O(log(количество битов)):

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

person barak manos    schedule 05.02.2014

arrow_upward
1
arrow_downward

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

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;
}
person Dietrich Epp    schedule 05.02.2014