位操作

Question

我正在学习位操作并遇到以下代码。我正在尝试弄清楚它的作用：

long func_c(unsigned long x) {
  long val = 0;


  // sums of bits in x (done in parallel for each byte segment)
  for (int i = 0; i < 8; i++) {
    val += (x & 0x0101010101010101L);
    x >>= 1;
  }

  // adds the top 32 bits to the lowest 32 but why?
  val >>= (val >> 32);
// adds the top 16 bits to the lowest 16 but why?
  val >>= (val >> 16);
// adds the top 8 bits to the lowest 8 but why?
  val >>= (val >> 8);

  // gets the lowest byte
  return val & 0xff;
}

一系列右移试图实现什么目标？

Answer 1

for

循环在

val

中创建一组8个字节，每个字节包含

x

相应字节中“1”位的数量。

所以请记住，我们试图获取原始

x

中“1”位的数量，到目前为止，我们所拥有的只是

val

的字节 0，其中包含 x 的字节 0 中“1”位的数量， val 的字节 1 是 x 的字节 1 中“1”位的数量，依此类推。因此我们要将

val

的 8 个字节加在一起。

通过将

val

的高 4 个字节添加到

val

的低 4 个字节，代码获得了一些额外的并行性。请记住，每个字节的最大值为 8，因此当您将这两个 32 位值相加时，每个字节都会添加到相应的其他字节而不会溢出。因此，32 位结果现在具有原始字节的部分和

val

。

然后，通过将 32 位结果拆分为两个 16 位值并将它们相加来获得更多并行性。再次，相应的字节被加在一起而不会溢出。

最后将 16 位数字的两半相加，得到原始中“1”位的总数

x

。