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

Я пытаюсь найти четность битовой строки, так что она возвращает 1, если x имеет нечетное число из 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; } 

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

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

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

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

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

    Бит-четность может быть выполнена следующим образом:

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