2020q3 Homework3 (quiz3)

contributed by < fwfly >

測驗 1

題目要求 :
在 c 語言的規格中，對於負數的向右位移是 implementation-defined ．

實作一個可運算有號數的向右位移

測驗 2

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_ctz(num) & 0x1);  
}

(num & (num - 1))==0 ?

4 的 bitwise 表示為 0100
而 4 的次方相當於向左位移 2 個 bits ( <<2 )
所以只要是 4 的次方．
裡面都會只有一個 bit 為 1．

0000 0100 // 4
0001 0000 // 16
0100 0000 // 64
...

透過 (num & (num - 1))==0 可以知道這個數字是不是存在唯一一個為 1 的 bit

但是如果單純這樣檢查，其實也會把 2 或者 8 的次方算進去．所以需要透過額外的方式去判斷是否為 4 的次方

實驗

int isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0;
}

int main()
{
   int test_num = 2;
   int res = isPowerOfFour(test_num);
   printf("%d: %d\n", test_num, res);
   test_num = 4;
   res = isPowerOfFour(test_num);
   printf("%d: %d\n", test_num, res);
   test_num = 7;
   res = isPowerOfFour(test_num);
   printf("%d: %d\n", test_num, res);
   test_num = 8;
   res = isPowerOfFour(test_num);
   printf("%d: %d\n", test_num, res);
   test_num = 9;
   res = isPowerOfFour(test_num);
   printf("%d: %d\n", test_num, res);
}

可以看到 2 跟 8 被認為是 4 的次方

2: 1
4: 1
7: 0
8: 1
9: 0

!(__builtin_ctz(num) & 0x1)

如果用 __builtin_ctz 去跑 4 次方的倍數則會得到

4:   2 
16:  4
64:  6
256: 8
...

也就是從右邊數來（直到碰到第一個為 1 的 bit ） 0 bits 的個數都會剛好是 2 的倍數，也就是第一個 bit 為 0

2: 0010
4: 0100
6: 0110
8: 1000
...

所以 & 0x1 再取 not 的意思就是第一個 bit 不等於 1
因此加上這個條件就可以得知是否為 4 的次方數

測驗 3

leedcode 的問題是給定一個數字，計算在幾次的運算後會歸零 ?
運算方式有兩種 :

1. 如果是偶數做除 2
2. 如果是奇數做減 1

問題可以轉換成

1. 要做多少次位移 ( >>1 )，因為向右位移 1 位，等於做除 2
2. 要減多少次 1

先放上答案

int numberOfSteps (int num)
{
    return num ? __builtin_popcount(num) + 31 - __builtin_clz(num) : 0;
}

這邊有兩個 gcc 函式對應的則是上面兩種運算方式

要做多少次位移 (要除 2 多少次)?

下面的程式碼可以解決這樣的問題

31 - __builtin_clz(num)

假定數字大小為 32 位元，因為最後一位數不做位移，所以最多會做 31 次，假設碰到 (0xFFF…FF)
剩下的問題是從第幾個 bit 開始做位移 ？
這個問題可以換成
最左邊為 1 的 bit 前面有多少個 0 ?

000000000000000000000000 10100101 // 有 24 個 0

__builtin_clz 可以幫忙做這樣的運算

__builtin_clz

根據測驗 2 的題目描述可知
這個 function 是 return 有多少個 leading 0
因為前面的 0 可以不用做運算，所以扣掉前面 bit 為 0 的個數，就可以知道剩下有多少個 bits 要做位移運算

比方說

int x = 165; // 00000000000000000000000010100101

第 25 個 bit 是 1，前面 24 位是 0．
所以需要做 31 - 24 = 7 次位移 ( >>1 )

10100101   // 第 1 次位移
1010010    // 第 2 次位移
101001     // 3
10100      // 4
1010       // 5
101        // 6
10         // 7
1          // 不做位移

要減多少次 1 ?

上面算完了位移，再來是要算減 1
減 1 可以想像成最右邊的 bit 為 1 的次數．
同上面的例子

10100101  // 165 最右邊 bit 為 1
1010010   // 82  偶數
101001    // 41  最右邊 bit 為 1
10100     // 20  偶數
1010      // 10  偶數
101       // 5   最右邊 bit 為 1
10        // 2   偶數
1         // 1   最右邊 bit 為 1

透過位移可以看到會有四次為 1 的狀態，所以會減 4 次．
而這個 4 次剛好就會等於 10100101 裡面 bit 為 1 的個數．

從原題目可以得知 __builtin_popcount 是用來算一個數字裡面有多少個 bits 為 1
所以再把 __builtin_popcount 數字加回去來得到答案．