CSAPP HW 2.65、2.66

---

P 131 homework 2.65, 2.66非常有趣。我的做法是，一个用分治法，不断取相邻的1；另一个，就是受2.65的启发，变成[0...0 1...1]。(当然，不知道有无漏洞。。233）

// hw 2.65, 2.66
#include <stdio.h>
#include <stdlib.h>

// 2.65 : test if x own odd 1s
int odd_ones(unsigned x) {
  x ^= x >> 1;
  x ^= x >> 2;
  x ^= x >> 4;
  x ^= x >> 8;
  x ^= x >> 16;
  return x & 1;
}
// 2.66: most significant bit
int MSB(unsigned x) {
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return x - (x >> 1);
}
int main(int argc, char const *argv[]) {
  printf("%d\n", odd_ones(0xfffE));
  printf("%x\n", MSB(0x6600));
  return 0;
}
/**
 * result: 
 * 1
 * 4000
 */

@ping1008 在 CSAPP HW 2.65、2.66 中说：

#include <stdio.h>
#include <stdlib.h>

// 2.65 : test if x own odd 1s
int odd_ones(unsigned x) {
x ^= x >> 1;
x ^= x >> 2;
x ^= x >> 4;
x ^= x >> 8;
x ^= x >> 16;
return x & 1;
}

我认为应该改成

  x ^= x >> 16;
  x ^= x >> 8;
  x ^= x >> 4;
  x ^= x >> 2;
  x ^= x >> 1;

也就是反复平移过去xor，如果重叠的位置都是1，则可以消去（xor结果为0），那些重叠位置不都是1在结果中该位置就变成1，记录了没有消去的1，反复进行，随着平移的进行，反复消去成对的1，最后的结果如果是1则是odd

我感觉这两种结果应该一致，尽管用了不同的方法理解。第二种是往后不断对折，消除相同的。第一种是两两消除、四个四个抵消……理论上应该得到相同的结果。选取个别数字进行测试，可以通过。

搞错了，一直想成lab那道类似的计数 囧

2333……

HW 2.65 其实就是计算 bit parity
在 stanford 的 bithacks 里还有几种做法

可以可以。回头看看。$E = MC^2$