1

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

* 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;
}
4

2 回答 2

10

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

假设 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 代表mask，而 4 & 1 分别指4 bytes 和1 byte

然后棘手的部分是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 位段您有：

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

从那里可以清楚地看出，上面添加 8 个元素的结果将在 0 到 8 之间。

也就是说，每个 8 位段将获得 0000 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 个字节中的位数的总和。

（总和我想这就是变量中的s代表的 - 总和）

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 中将这四个字节中的结果组合起来以找到一个字节中的总和

（我想，这就是s1的意思：sum in one byte）

您通过以下方式获得 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 表示全部为 8），即位数1 在变量 x 中。因此该函数被命名为bitCount。

这就是函数的工作原理。

最后说明：知道这一点，您甚至可以将 m1 更改为 0x0F（而不是 0xFF），结果仍然相同。

于 2016-02-04T06:13:54.837 回答
0

在此声明之后：

    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 的数量，然后将 s4 右移到 8 位将给出 x 的字节 2 中 2 的数量，依此类推 4 字节。然后将所有相加将给出 x 中 1 的数量。

于 2016-02-04T08:45:01.447 回答