Вопрос с битого сайта

Question

Вот код:

unsigned int v;  // word value to compute the parity of
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

Он вычисляет четность данного слова, v. Что означает значение 0x6996?

Число 0x6996 в двоичном виде: 110100110010110.

Answer 1

Первые четыре строки преобразуют v в 4-битное число (от 0 до 15), которое имеет ту же четность, что и оригинал. 16-битное число 0x6996 содержит четность всех чисел от 0 до 15, а сдвиг вправо используется для выбора правильного бита. Это похоже на использование таблицы поиска:

//This array contains the parity of the numbers 0 to 15
char parities[16] = {0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0};
return parities[v];

Обратите внимание, что записи массива совпадают с битами 0x6996. Использование (0x6996 >> v) & 1 дает тот же результат, но не требует доступа к памяти.

Answer 2

Хорошо, алгоритм сжимает 32-битное int в 4-битное значение той же четности с помощью последовательных битовых OR, а затем AND с 0xf, так что в младших значащих 4-битах присутствуют только положительные биты. Другими словами, после строки 5 v будет целым числом от 0 до 15 включительно.

Затем он смещает это магическое число (0x6996) вправо на это значение 0-16 и возвращает только младший значащий бит (& 1).

Это означает, что если в позиции v в 0x6996 есть 1, то вычисленный бит четности равен 1, в противном случае он равен 0 - например, если в строке 5 v вычисляется как 2, то `возвращается, если это было 3, тогда возвращалось бы 0.