Генерация таблицы поиска четности

Question

Я читал битовые тидлинговые хаки для вычисления четности по этой ссылке: Битовые тидлинговые хаки

Для вычисления четности есть метод поиска, который генерирует таблицу четности для целых чисел от 0 до255 с 5 кодами линии.

#define P2(n) n, n ^ 1, n ^ 1, n 
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n) 
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n) 
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)

unsigned int table[256] = { LOOK_UP };

Я проверил значения P2 (n) и P4 (n), которые вычисляют четность для [0..15].Но я не понял интуицию за этими строками кода.Как эти строки вычисляют четность [0..255]?Я хочу знать интуицию и теорию этого рекурсивного подхода.Заранее спасибо.

Answer 1

Для P2 четность бита, установленного в 1, тривиальна:

0b00 -> 0
0b01 -> 1
0b10 -> 1
0b11 -> 0

Prepend 00 не меняет четность,
, но prepend next 01 меняет четность:

0b0100 -> 1 // 0 ^ 1
0b0101 -> 0 // 1 ^ 1
0b0110 -> 0 // 1 ^ 1
0b0111 -> 1 // 0 ^ 1

Четность 0b10.. совпадает с 0b01.. и снова изменится с 0b11..

n ^ 1 разрешить переключение:

n | n ^ 1
--|--------
0 | 1
1 | 0

или !n Возможно, была выбрана или другая формула с той же таблицей

Надеюсь, вы видите образец сейчас.