看csapp看到的一段不理解的C语言代码...

Question

代码如下图所示 :

这是原书对它的解释, 但是我看了解释还是不太理解... 求大神帮忙解惑 ...

Answer 1

long fun_c1(unsigned long x) {
    unsigned char vx[8];
    unsigned char val[8] = {0};
    int i, j;
    for (i = 0; i < 8; i++) {
        vx[i] = (x >> (i * 8)) & 0xFF;
    }
    for (i = 0; i < 8; i++) {
        for (j = 0; j < 8; j++) {
            val[i] += vx[i] & 0x01;
            vx[i] >>= 1;
        }
    }
    for (i = 1; i < 8; i++) {
        val[0] += val[i];
    }
    return val[0];
}

上面这段程序把x拆成8个char存到数组vx中并分别统计这8个char中1的个数存放到val数组中，再最后统计val数组中8个数的和。
我们可以发现func_c1()第8行开始的双重循环，其外循环每次的迭代是各自独立的，亦即如果我们有8个处理器同时进行 i = 0, i = 1, i = 2, ... i = 7 的处理也不会导致运算结果出错，因而这里就可以写成val的8个字节同时加上vx的8个字节对应字节的末位再将vx的8个字节同时右移也是等效的。但是如果整体按照unsigned long集体处理的话，要考虑到加法的进位问题和右移的“污染”问题（高位字节的数据会右移进低位字节），所幸：一、64位整数任意一段最多只有64个1，所以给定8位（1字节）的val[i]无论怎么统计都不会溢出；二、由于实际上val[i]是每次加上了vx[i]的最低位，而且读取先于右移，所以合并成一个大的unsinged long右移后虽然最后一次右移会使得x的高字节的最低位占据低一个字节的最低位，但循环已经结束，x的值已经没有意义了。
最后第13行的统计，比起这样直接统计，假定我们有多个处理器的话，有一种并行统计的方法就是：

val[0] val[1] val[2] val[3] val[4] val[5] val[6] val[7]
  \      /      \      /      \      /      \      /
   \    /        \    /        \    /        \    /
    \  /          \  /          \  /          \  /
    sum1[0]       sum1[1]       sum1[2]       sum1[3]
      \             /             \             /
       \           /               \           /
        \         /                 \         /
         \       /                   \       /
          \     /                     \     /
           \   /                       \   / 
           sum2[0]                     sum2[1]
             \                           /
              \                         /
               \                       /
                \                     /
                 \                   /
                  \                 /
                   \               /
                    \             /
                     \           /
                      \         /
                       \       /
                        \     /
                         \   /
                          sum

由于每一层统计之间互相不影响，所以我们也可以用val[2 * i]来存sum1[i]，val[4 * i]来存sum2[i]，val[0]来存sum仍然不影响正确性。但是这样就可以把程序写得像原书fun_c()最后的3个连加一样简洁高效了。当然最后返回第一个字节的值（fun_c1()中是val[0]而fun_c()中是val & 0xFF）作为结果。