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

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

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

  • Правильно ли это решение проблемы? Я предполагаю, что моя проблема связана с первой операцией, в частности (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;
}

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 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");
    }
}