BITCOUNT宏需要解释

Question

Can someone explain how this works?

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


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

Clarification:

Ideally, the answer will start something along the lines of:

The macro: "BX_" subtracts three values from the passed in number.

These three values represent:

1. XXXXX
2. YYYYY
3. ZZZZZ

This allows the BITCOUNT() to work as follows...

Cheers,

David

- user227479

---

你选择了你最喜欢的8位十六进制数并手动运行宏来看看结果了吗？如果没有，请尝试一下。 - John

不 - 我更希望回答我提出的问题，而不是回答者对我最好做什么的假设。 - user227479

对你最有益的是更好地掌握理解问题的能力，不要懒惰思考，也不要仅仅学会如何向他人提问。 - GManNickG

@GMan：不过你没必要这么刻薄。如果我问：“光学鼠标是如何工作的？”你会告诉我光线如何在桌面上反射，还是让我别那么懒，自己拆开鼠标去研究呢？ - Steve Jessop

我不认为我表现得很讨厌。你的比喻是错误的。 - GManNickG

Answer 1

BX_(x) 的输出是每个十六进制数字中的1位数。因此

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.

- John

Answer 2

正如Johannes在那个精彩的Bit Twiddling Hacks页面中引用的那样，AMD的Software Optimization Guide for AMD Athlon™ 64 and Opteron™ Processors在第179和180页（对应于PDF的第195和196页）中有关于该算法的优秀而详细的描述。

此外，this page也描述了相同的想法以及一些替代方案及其相对性能。

- fvu