有人能解释一下这个bitCount代码是如何工作的吗？

Question

这是我的助教帮助我得到的代码，但后来我完全忘记了它是如何工作的，因为我似乎无法得到正确的答案，面试评分是明天。如果有人能帮忙，请帮忙。谢谢

* bitCount - returns count of number of 1's in word
*   Examples: bitCount(5) = 2, bitCount(7) = 3
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 40
*   Rating: 4
*/
int bitCount(int x) {
    int m4 = 0x1 | (0x1<<8) | (0x1<<16) | (0x1<<24);
    int m1 = 0xFF; 
    int s4 = (x&m4) + ((x>>1)&m4) + ((x>>2)&m4) + ((x>>3)&m4) + ((x>>4)&m4) + ((x>>5)&m4) + ((x>>6)&m4) + ((x>>7)&m4);
    int s1 = (s4&m1) + ((s4>>8)&m1) + ((s4>>16)&m1) + ((s4>>24)&m1);
    return s1;
}

Answer 1

当您将与位相关的操作转换为它的位表示时，通常更容易看到它发生了什么：

假设int是32位，那么下面是m4 & m1在其位表示中的内容：

0000 0001 0000 0001 0000 0001 0000 0001 //m4, masking across the 4 bytes
0000 0000 0000 0000 0000 0000 1111 1111 //m1, masking only 1 byte, the Least Significant Byte (LSB)

我认为m代表掩码__，而4和1分别指4字节和1字节。

然后，棘手的部分是s4。您可能需要一步一步地检查它，以便了解它是什么。

首先，注意右位移位和m4掩蔽：

pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000w 0000 000w 0000 000w 0000 000w //x&m4

pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 1
0pqr stuv wpqr stuv wpqr stuv wpqr stuv // x >> 1
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
pqrs tuvw pqrs tuvw pqrs tuvw pqrs tuvw // x
---------------------------------------- >> 7
0000 000p qrst uvwp qrst uvwp qrst uvwp // x >> 7
0000 0001 0000 0001 0000 0001 0000 0001 //m4
---------------------------------------- &
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4

其次，请注意从上述结果中得到的8种元素的添加：

0000 000w 0000 000w 0000 000w 0000 000w //x&m4
0000 000v 0000 000v 0000 000v 0000 000v //(x>>1)&m4
.
.
0000 000p 0000 000p 0000 000p 0000 000p //(x>>7)&m4
---------------------------------------- +
//Resulting in s4

因此，由于p到w每个只能是0或1，并且有8个这样的元素，因此，每8位段就有：

p+q+r+s+t+u+v+w // each element is either 0 or 1

从这里可以清楚地看到，上面添加的8个元素的结果从0到8不等。

也就是说，每8位段将得到0000 (小数表示为0，如果为0)到0000 1000 (小数表示为8，如果为1)。

因此，您将获得以下格式的s4：

0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4

其中abcd、efgh、ijkl和mnop是每个字节添加p到w的结果。

现在，请注意，您得到了x中分布在4个字节上的位数的和。

(__sum，我想这就是变量中s所代表的- sum)。

0000 abcd //byte 1, left most, MSB
0000 efgh //byte 2, second from left
0000 ijkl //byte 3, second from right
0000 mnop //byte 4, rightmost, LSB

因此，您需要将s4中这四个字节的结果组合起来，以便在one字节中找到sum。

(我想，这就是s1的意思:在一个字节__中的和)

您通过以下方法获得s1：

1. 用0，8，16，24移动s4
2. 用0xFF掩蔽他们每一个
3. 并结合(添加)结果。

因此，发生以下操作(在位级)：

0000 abcd 0000 efgh 0000 ijkl 0000 mnop // s4
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 mnop

0000 0000 0000 abcd 0000 efgh 0000 ijkl // s4 >> 8
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 ijkl

.
.

0000 0000 0000 0000 0000 0000 0000 abcd // s4 >> 24
0000 0000 0000 0000 0000 0000 1111 1111 //m1 
--------------------------------------- &
0000 0000 0000 0000 0000 0000 0000 abcd

可以看出，您只需添加以下四个元素：

0000 0000 0000 0000 0000 0000 0000 mnop //0 to 8
0000 0000 0000 0000 0000 0000 0000 ijkl //0 to 8
0000 0000 0000 0000 0000 0000 0000 efgh //0 to 8
0000 0000 0000 0000 0000 0000 0000 abcd //0 to 8
--------------------------------------- +
//Final result, s1

您只需简单地添加四个数字，每个数字的值为0到8。因此，它必须得到一个0到32的值(0是所有值为0，32为all为8)，即变量x中的位1的数目，因此函数被命名为bitCount。

这就是函数的工作方式。

最后注意:知道这一点，您甚至可以用0x0F (而不是0xFF)更改m1，结果仍然是一样的。

Answer 2

在本声明之后：

    int s4 = (x&m4) + ((x>>1)&m4) + ((x>>2)&m4) + ((x>>3)&m4) + ((x>>4)&m4) + ((x>>5)&m4) + ((x>>6)&m4) + ((x>>7)&m4);

由于S4中有4个字节，那么其中的1个字节在相应的x字节中有1个字节，因此很明显，s4的每个字节在x的对应字节中都有1的字节数。

在语句中: int s1 = (s4&m1) + ((s4>>8)&m1) + ((s4>>16)&m1) + ((s4>>24)&m1)；

现在，s4的1字节在x的对应字节中有1's的个数，然后将s4右移到8位，就会给出x的字节2中的2's的个数，这样就可以得到4个字节。然后加上所有，就会得到x中的1的个数。