Проверьте четность по байту - PullRequest
Новая
       41

Проверьте четность по байту

1 голос
/ 22 мая 2019

Я нашел фрагмент кода в Stackoverflow и отредактировал его для своих нужд. source: Как проверить, имеет ли значение четную четность битов или нечетную?

Это работает как шарм, но я не могу понять, ПОЧЕМУ это работает.

Я попытался записать это, например, байт 0b01101101. 

   01101101
   00000110
   -------- ^
   01101011
   00011010
   -------- ^
   01110001
   00111000
   -------- ^
   01001001

Пока мой юнит тест дает ответ; 1 

uint8_t check_even_parity(uint8_t value){
     value ^= value >> 4;
     value ^= value >> 2;
     value ^= value >> 1;

     return value & 1;
}

Ожидается; 0 Фактический результат при попытке выписать его; 01001001

Ответы [ 2 ]

2 голосов
/ 22 мая 2019

Я хотел бы предложить метафору, которая может дать некоторую интуицию:

Представьте, что перед вами лежат 4 карты, которые вам нужно накапливать.Как человек с двумя руками, вы можете взять карту в каждую руку одновременно и положить их поверх других 2, затем взять одну из пар и положить ее поверх другой.

Этоскладывает 4 карты за 2 хода.

Теперь представьте, что вам нужно сложить 32 карты и иметь 16 рук (или больше).Вы можете использовать ту же технику: создать 16 стопок из 2 карт, затем 8 стопок из 4 карт, 4 стопки из 8 карт, 2 стопки из 16 карт и, наконец, одну стопку из 32 карт.

Это стопки 32карты за 5 ходов.

Теперь замените «стопку» на «xor», «карты» на «биты» и «руки» с возможностями процессора.За 5 смен и xors вы получите 32 бита числа, скомбинированного вместе, что дает 0, если число имеет четную четность, и 1 в противном случае.

2 голосов
/ 22 мая 2019

Каждый шаг объединяет два набора битов L и R так, что четность L объединяется с R.R в конечном итоге имеет ту же четность, что и L + R.

На шаге 1 мы берем 8 бит и получаем 4-битное число с той же четностью, что и 8-битное.На шаге 2 мы производим 2-битное число с той же четностью, что и 4. На последнем шаге мы производим 1-битное число с той же четностью, что и 2. Это означает, что за три шага мы получаем один бит с тем жепаритет как оригинал 8.

Позвольте мне показать вам, что я имею в виду один шаг за раз.(0110) и R - это право 4 (1101). 

xxxx1101 (R)
xxxx0110 (L)
--------
xxxx1011 (R^L)

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

L четно, а R нечетно, что означает, что L + R нечетно.Поэтому R ^ = L должен оставить R с нечетной четностью.Является ли?Это действительно так.0110 имеет два заданных бита, поэтому R ^ = 0110 переворачивает два бита R.Переключение четного числа битов не изменит четности.R остается нечетным .

На втором шаге L - это 2 левых бита (10), а R - это 2 правых (11).

xxxxxx11 (R)
xxxxxx10 (L)
--------
xxxxxx01 (L^R)

Теперь шесть битов исключены.Нас интересуют только два бита от каждого числа.

На этот раз L нечетное, а R четное.В совокупности L + R нечетно, поэтому на этот раз нам нужно изменить четность R.R ^ = L делает это?Опять же, это так.У L установлено нечетное количество битов, поэтому при выполнении XOR будет отображаться нечетное количество битов R, гарантируя, что четность R переключается.R становится нечетным .

На последнем шаге L и R - всего 1 бит на единицу.

xxxxxxx1 (L)
xxxxxxx0 (R)
--------
xxxxxxx1 (L^R)

L равно 1, R равно 0. Как и в предыдущих шагах, мы надеемся, что R ^ = L нечетно, и это так.R нечетно .

Замечательно.Мы начали с 8 битов с нечетной четностью и, успешно объединив две половинки, получили 1 бит с одинаковой четностью.

...