看csapp看到的一段不理解的C语言代码...
问题描述
代码如下图所示 :
这是原书对它的解释, 但是我看了解释还是不太理解... 求大神帮忙解惑 ...
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
)作为结果。
这篇关于看csapp看到的一段不理解的C语言代码...的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!