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()按如下方式工作......

干杯,

大卫

Answer 1

BX_(x)的输出是每个十六进制数字中的on位数.所以

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.

只需用(255 + 1)替换每个256即可

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

最后的观察(我用2位数的例子在地毯下扫描)V + W + X + Y总是小于255,所以

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