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

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

c parity bit-manipulation bit
person tippenein    schedule 23.09.2011    source источник
comment
Где вы нашли этот алгоритм?   -  person rnunes    schedule 23.09.2011
comment
не используйте int, будет переполнение, и тогда это поведение undefined. Вместо этого используйте unsigned и 1u, здесь перенос четко определен.   -  person Jens Gustedt    schedule 23.09.2011
comment
Этот алгоритм не работает. Он возвращает 1 для всех значений от 0 до 255.   -  person undur_gongor    schedule 23.09.2011
comment
Я взял нечетные битовые двоичные числа и объединил их по схеме XOR, AND и OR с самими собой минус 1, и XOR был единственным, который дал что-то полезное (по крайней мере, я так думал).   -  person tippenein    schedule 23.09.2011
comment
Возможный дубликат bitParity - поиск нечетного количества битов в целом числе< /а>   -  person Troyseph    schedule 27.10.2015

Ответы (3)


arrow_upward
3
arrow_downward

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

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

ОБНОВЛЕНИЕ: учитывая (странные и раздражающие) ограничения, мой ответ, вероятно, будет заключаться в том, чтобы расслабиться. цикл, указанный в решении "naive" для < страница href="http://graphics.stanford.edu/~seander/bithacks.html" rel="nofollow">bithacks. Это было бы некрасиво, но тогда я мог бы заняться чем-нибудь полезным. :)

person unwind    schedule 23.09.2011
comment
Я бы, конечно, использовал цикл для легкого подсчета каждого бита или даже просто XOR всех битов вместе, но для этого назначения мне не разрешено использовать управляющие структуры. Просто | ^ & ›› ‹‹ ~ + ! Итак, ваш ответ был моей непосредственной реакцией на это, но не в костях. - person tippenein; 23.09.2011
comment
Я взял ранее написанный код для подсчета битов и просто объединил результат с 0x1, чтобы увидеть, есть ли нечетное количество битов или нет. Однако я сделал алгоритм bitCount(int x) с помощью грубой силы; проверил каждый бит с помощью !!(x & (1‹‹bit#)) На данный момент мне этого недостаточно, но проблема битовой четности была решена на данный момент. - person tippenein; 23.09.2011

arrow_upward
4
arrow_downward

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

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

person Paul R    schedule 23.09.2011
comment
Я понимаю, что мой полный код не работает, но x ^ (x-1), казалось, давал ответы, которые имели смысл для значений, которые я пробовал. Если ты прав, то я должен просто бросить это и начать сначала. - person tippenein; 23.09.2011
comment
Просто попробуйте ввести значения 0, 1, 2 и 3, и вы увидите, что это не сработает. - person Paul R; 23.09.2011

arrow_upward
1
arrow_downward

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

#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");
    }
}
person sastanin    schedule 23.09.2011