下次的第二章小结会以浮点数结束。
这几天重新看CS:APP,一直在想一个问题,那就是究竟什么才算 “优秀的程序员”?
下午突然有所感想,那时正在看《编程珠玑》(Programming Pearls),第一章习题中的答案似乎不太准确(P196页 C下使用位向量的举例):
#defien BITSPERWORD 32
#defien SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[ 1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK));}
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK));}
int test(int i) { return a[i>>SHIFT] & (1<<(i & MASK));}
当出现负数时会如何?随后我又否定了自己的观点,因为题意中标注只会有正整数。可是如果是负数呢?
那么很可惜算数位移并不会对他造成太大的偏差,因为填充的最高位被新的次高位抵消一半,而整体权值下降一半。
却需要重新定义数组了。
想到这个问题确实是因为重新看了第二章的缘故。
另外这里还有一点小彩蛋。
有么有真正想过CPU对于你的代码的时间消费呢?
CS:APP里面提到:
加法,减法,位级运算,位移 只需要1个时钟周期
乘法需要至少 12个时钟周期
除法需要至少 30个时钟周期
所以GCC编译器很喜欢尽可能的将乘除换成左右位移 🙂
例如
result = X*M + Y/N;
return return;
>>GCC to >>
int t X;
X << 4;
X -= t;
if (Y < 0) Y += 3;
Y >>= 2;
return X+Y;
猜猜M,N是多少? (提示:对于二进制补码左移,如果X < 0 需要在位移前偏置(biasing), 即加上2^k-1)