Требуется объяснение для макроса BITCOUNT

Question

Может кто-нибудь объяснить, как это работает?

#define  BX_(x)         ((x) - (((x)>>1)&0x77777777)                    \
                             - (((x)>>2)&0x33333333)                    \
                             - (((x)>>3)&0x11111111))


#define BITCOUNT(x)     (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)

Пояснение:

В идеале, ответ будет начинаться примерно так:

Макрос: "BX_" вычитает три значения из переданного числа.

Эти три значения представляют:

1. XXXXX
2. YYYYY
3. ZZZZZ

Это позволяет BITCOUNT () работать следующим образом ...

Приветствия

David

Answer 1

Выход BX_ (x) - это число битов в каждой шестнадцатеричной цифре. Так

BX_(0x0123457F) = 0x01121234

Следующее:

((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F)

перетасовывает счет в байты:

((BX_(0x0123457F)+(BX_(0x0123457F)>>4)) & 0x0F0F0F0F) = 0x01030307

Принимая этот результат, по модулю 255 складываются отдельные байты для получения правильного ответа 14. Чтобы убедиться, что это работает, рассмотрим только двухбайтовое целое число, 256 * X + Y. Это всего лишь 255 * X + X + Y, а 255 * X% 255 всегда равно нулю, поэтому

(256*X + Y) % 255 = (X + Y) % 255.

Это распространяется на четырехбайтовые целые числа:

256 ^ 3 * V + 256 ^ 2 * W + 256 * X + Y

Просто замените каждые 256 на (255 + 1), чтобы увидеть, что

(256^3*V + 256^2*W + 256*X + Y) % 255 = (V + W + X + Y) % 255.

Последнее замечание (которое я рассмотрел на примере двузначного примера) состоит в том, что V + W + X + Y всегда меньше 255, поэтому

(V + W + X + Y) % 255 = V + W + X + Y.

Answer 2

Как цитирует Йоханнес со страницы Bit Twiddling Hacks , превосходное и подробное описание этого алгоритма приведено в Руководстве по оптимизации программного обеспечения для процессоров AMD Athlon ™ 64 и Opteron ™ от AMD на страницах № 179 и 180 - в соответствии со страницами 195 и 196 документа PDF.

Также описывается та же идея и некоторые альтернативные решения и их относительная производительность: эта страница .