c++ - 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. 年年年
3. ZZZZZ

这允许 BITCOUNT() 如下工作......

干杯，

大卫

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.

最后的观察结果(我用 2 位数的例子掩盖了这一点)是 V + W + X + Y 总是小于 255，所以

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