深入理解计算机系统——第二章小结(3)

下次的第二章小结会以浮点数结束。
这几天重新看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）