CSAPP(1):數字的計算機表示——課後題，csapp課後

CSAPP(1):數字的計算機表示——課後題，csapp課後

2.65

int even_ones(unsigned x)

要求：return 1 when x contains an even number of 1s; 0 otherwise. 假設int 有 w=32位。

分析：最應該使用的是循環，但是循環語句不能使用。如果一個一個的寫成語句，需要32次；這裡使用二分法，那麼操作就變成了Log2³² =5次。二分法蘊含了循環同時簡化了循環遍歷。如何使用二分法？

  題目是判斷x中1的奇偶數，可以將x一分為2，前16位x1與後16位x2，x3=x1^x2，則，如果x有偶數個1，x3必定有偶數個1；如果x有奇數個1，x3必定有奇數個。

int even_ones(unsigned x)
{
     x ^= (x >> 16);
     x ^= (x >> 8);
     x ^= (x >> 4);
     x ^= (x >> 2);
     x ^= (x >> 1);
     return !(x & 1);    
}

2.66

int leftmost_one(unsigned x)

要求: generate mask indicating leftmost 1 in x. assume w=32; if x=0, then return 0;

提示：先將x轉換成形如[0..011..1]的位向量

分析：這裡就是尋找最高位的1在位向量x中是第幾位，應該使用循環，然後循環不能用，這裡使用二分法。首先，如【提示】中，先將x轉換成形如[0..011..1]的位向量，即：最高位1之後的所有位都變為1。

int leftmost_one(unsigned x)
{
     x |= x >> 1;
     x |= x >> 2;
     x |= x >> 4;
     x |= x >> 8;
     x |= x >> 16;
     x &= ~(x >> 1);
     return x;
}