关于C语言位操作代码中系列右移操作作用的技术问询

我正在学习位操作（Bit manipulations），遇到了如下C语言代码，正尝试分析其功能：

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

请问这些连续的右移操作旨在实现什么？

核心结论 #

这段代码的目的是计算unsigned long类型变量x的二进制中1的总个数（即汉明重量），而连续的右移操作是为了把前面并行统计的8组位的1的数量，快速汇总成一个总和。

分步解释 #

1. 前置循环的作用
   0x0101010101010101L是64位掩码，每8位的最低位为1。循环8次每次右移x一位，再和掩码按位与，会把x中每一组间隔8位的位（比如第0、8、16…56位；第1、9、17…57位，共8组）的1的数量，分别存在val的8个字节中。此时val的每个字节对应一组位的1的总数。

2. 连续右移的汇总逻辑

• val += (val >> 32)：把val的高32位（第4-7个字节）加到低32位（第0-3个字节），让低32位的每个字节变成「原字节 + 高32位对应位置字节」的和，此时低32位存了4组两个字节的和。
• val += (val >> 16)：把低32位的高16位（第2-3个字节）加到低16位（第0-1个字节），让低16位的每个字节变成「之前的两个字节和 + 另外两个字节和」的总和，此时低16位存了2组四个字节的和。
• val += (val >> 8)：把低16位的高8位（第1个字节）加到低8位（第0个字节），最终低8位就得到了所有8组位的1的总数量。

最后val & 0xff取出这个总数量，因为64位变量中1的总数最多是64，完全能存进一个字节里。

内容的提问来源于stack exchange，提问作者testing09