объяснение битовой четности

Мне нужно создать функцию bitParity(int x), которая принимает целое число и возвращает 1, если в битовой форме x есть нечетное количество нулей, и 0 в противном случае.

Пример: bitParity(5) = 0, bitParity(7) = 1 Допустимые действия: ! ~ & ^ | + ‹‹ >>

Мой приятель поделился со мной своим кодом, но когда я сделал расчет с нуля, он, кажется, получил противоположное тому, что он получил, может кто-нибудь немного объяснить этот код, чтобы я понял, как он работает?

int bitParity(int x) {
x = ( x >> 16 ) ^ x;
x = ( x >> 8 ) ^ x;
x = ( x >> 4 ) ^ x;
x = ( x >> 2 ) ^ x;
x = ( x >> 1 ) ^ x;

    return (x & 1);
}

c parity bit
person user3221217    schedule 03.02.2014    source источник
comment
Поведение ›› для значений со знаком не указано. Поэтому вам лучше сделать аргумент unsigned, если вы хотите получить предсказуемый результат.   -  person Hans Passant    schedule 03.02.2014

Ответы (1)


arrow_upward
0
arrow_downward

Эта функция в основном xor обрабатывает все биты входного числа и помещает его в LSB, поэтому дает 1, если есть нечетное количество 1s.

Как это работает:

  • Возьмите ввод 8-bit, скажем 11001001.
  • Для ввода 8-bit вам нужно начать с 3-го оператора кода: x = ( x >> 4 ) ^ x;

  • Выполняя это (Шаг 1), вы получаете:

    х7 х6 х5 х4 х7^x 3 х6^x2 х5^x1 х4^х0

где xi обозначает ith бит x.

  • Теперь Шаг 2: x = ( x >> 2 ) ^ x; дает:

    x6^x2^x4^x0 в младшем разряде x и
    x 7^x3^x5^x1 в битовой позиции 1 из x. Положения для отдыха не имеют значения.

  • Шаг 3: x = ( x >> 1 ) ^ x;, который наконец дает:

    х6^x2^x4^x0^x7^ x3^x5^x1 в младшем разряде x.

  • Последний шаг: return (x & 1);, которое возвращает значение этого выражения, которое равно xor всех битов в x, что равно 1 тогда и только тогда, когда количество 1s в x нечетное.

  • Вы можете расширить это до номеров 16-bit, 32-bit или 64-bit.

  • Кроме того, обратите внимание, что нахождение нечетного числа 0s эквивалентно нахождению нечетного числа 1s, поскольку общее количество 1s и 0s в сумме дает четное количество битов.

  • Поэтому приведенный выше код должен работать правильно для вас.

person Don't You Worry Child    schedule 03.02.2014