Код четности для нечетного числа бит

Question

Я пытаюсь найти четность цепочки битов, чтобы она возвращала 1, если х имеет нечетное число из 0.
Я могу использовать только базовые побитовые операции, и то, что у меня есть, проходит большинство тестов, ноМне интересно 2 вещи:

1. Почему работает x ^ (x + ~ 1)?Я наткнулся на это, но, похоже, даст вам 1, если есть нечетное количество бит, и еще что-то, если даже.Как 7 ^ 6 = 1, потому что 7 = 0b0111

2. Это правильное направление решения проблемы для этого?Я предполагаю, что моя проблема проистекает из первой операции, в частности (x + ~ 1), потому что она будет переполнять определенные 2 числа дополнения.Спасибо

Код:

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

Ваша функция четности на самом деле не работает, насколько я могу судить - похоже, она дает правильный ответ примерно половину времени, что примерно так же хорошо, как возвращение случайного результата (или даже просто возвращение 0 или 1 всеговремя).

Существует несколько хаков на битовом уровне, с которыми do фактически работают: http://graphics.stanford.edu/~seander/bithacks.html#ParityNaive - вы, вероятно, захотите взглянуть на последний из них: http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel

Answer 2

Я бы использовал фактический подсчет, а не хаки на уровне битов, которые используют представление чисел, которые будут и чувствовать себя безопаснее, и будут более чистыми и понятными. Возможно, медленнее, конечно, но это довольно неплохой компромисс, особенно когда никто ничего не знает об ожидаемых результатах.

Для этого просто напишите код для подсчета числа в 1 бит, наиболее простое решение обычно сводится к циклу.

ОБНОВЛЕНИЕ: Учитывая (странные и раздражающие) ограничения, мой ответ, вероятно, будет развернуть цикл, данный в "наивном" решении на bithacks страница. Это было бы не красиво, но тогда я мог бы сделать что-нибудь полезное. :)

Answer 3

Битовая четность может быть сделана так:

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