§ Четность

Этот флаг предназначен, чтобы подсчитать, четное ли количество единиц в байте или нет. Если да - то флаг устанавливается в 1, если же нет - то в 0.
Флаг четности вычисляется с помощью последовательно применённых к каждому биту XOR. Почему так? Всё очень просто:
A B C
0 0 0
0 1 1
1 0 1
1 1 0
Здесь видно, что когда число единичных битов четно (либо 0 битов, либо 2 бита), то тогда выставляется 0, иначе 1.
Теперь, есть еще одно правило, которое гласит, что от перестановки сумм слагаемое не меняется. Поскольку XOR это сумма (без переноса), то слагаемое от его перестановки меняться никак не может. Это правило, которое может быть легко проверено где угодно, и когда угодно.

§ Как сосчитать?

Элементарно! Вообще, для 8-битного числа есть смысл составить таблицу, в которой за время доступа O(1) производится проверка на то, что число четное. Но таблицу, конечно, тоже надо заполнить.
Возьмем 8 бит (например число 00101101) и разделим на две части 0010 и 1101, после чего делается поразрядное XOR для каждого бита, то есть:
    0010
xor 1101
  = 1111
Как видно, получились все единицы.
  • Повторяем процедуру еще раз, делим полученное число на 2 части: "11" и "11" => 11^11 = 00.
  • Повторяется еще раз, делится на 2 части и получается "0"^"0"=0
Раз получилось 0, то значит, все число четное. Это значит, что пары единиц загасили друг друга в этом числе и получилось 0. Если переставить биты в исходном числе "00101101", например так "0000 11 11", то видно, что тут две пары единиц, которые взаимно уничтожаются, получая 0.
Если бы получился 1, это значит, что где-то есть единица, оставшаяся без пары и потому не аннигилировавшаяся в пустоту Бездны.

§ Код Си

int is_parity(unsigned char b) {

    unsigned char a = b;
    a ^= (a >> 4);    // Складываются биты a[i] = a[ 4+i ] ^ a[i], i=0..3
    a ^= (a >> 2);    // Складываются биты a[i] = a[ 2+i ] ^ a[i], i=0..1
    a ^= (a >> 1);    // Складываются биты a[i] = a[ 1   ] ^ a[0]
    return !(a & 1);  // Если бит a[0] == 0, то тогда 1, иначе 0
}
9 окт, 2021
© 2007-2022 Том плющит все права