今天看了一個問題，是叫你寫個程式判斷一個數字 n 是否為 2 的次方。

起初一個很簡單的概念就是用个迴圈，從 1 開始不斷的乘 2 ，如果這個數字跟叫你丟進來測試的數字 n 相同，那就是 2 的次方了。

大概長是下面這個樣子：

int det_is_power_by_2(unsigned n)
{
    for (unsigned i = 1; i <= MAX_OF_INT; i * 2) {
        if ( i == n )
            return 1;
            
    }
    
    return 0;
}

上面是個很淺顯易懂的作法，當然如果不想用乘法，也能用 i << 1 去做乘 2 的動作，在電腦裡二進位的左移剛好就是乘上 2 ，只有在數字乘到極限的時候，才有可能發生錯誤（溢位）。

不過後來我發現二進位的數學真的是一個沒有極限的領域，除了左移代表乘 2 ，右移代表除 2 的這個例子，剛剛判斷是否為 2 的次方數還能寫成如下的方法：

int det_is_power_by_2(unsigned n)
{
    return n && !(n & n - 1);
}

除了行數短，其實也隱含著很特殊的二進位數學的概念，我來解釋一下這段程式碼的原理，不過要先說明一下在傳統的程式語言領域通常 0 為 False，非 0 為 True ，所以一旦有語言無法使用這個概念，那這段 code 就起不了作用了。

首先：

n & n - 1

這裡的概念真的很酷，因為剛好二進位中，只要是 2 的次方，都剛好會是像 100 或者 1000 這種 1 開頭，尾巴都是 0 的狀況，而這種 2 的次方數減 1 之後，則剛好是 011 或者 0111 這種尾巴都剛好是 1 的狀況。

所以拿 8 來作舉例

8 的二進位 0b1000
7 的二進位 0b0111

一旦這兩個數字作每個 bit 間的 and 運算（也就是 & 運算），就會變成下面這樣：

0b1000
  &&&&
0b0111
-------------
  0000

也就是說結果一定會是 0 ，在電腦中代表 False

再來看一個普通一點的狀況，舉個數字 6 來看看是否為 2 的次方

6 的二進位 0b110
5 的二進位 0b101

0b110
  &&&
0b101
------------
  100

所以當中的結果 0b100 換算成十進位是 4 ，也就是非 0 的結果，所以是個代表 True 的結果

所以單純用 n & n - 1 來計算是否為 2 的次方，若剛好是 2 的次方的話會是 False ，不是 2 的次方剛好會是 True，所以只要在這個前面加個 not 來把運算結果給反過來就行了，所以就是 !(n & n - 1)

只不過有個狀況會是個要注意的例外，因為數學當中規定 0 不是任何人的次方，但是根據這種方法去運算， 0 跟 -1 依然得到 True，其中的原理是關於 -1 在二進位裡頭是滿滿的 1 ，假設是 8 位元整數那就是 0b11111111 ，所以滿滿的 1 跟滿滿的 0 去計算結果依然會告訴你 0 是 2 的次方數。

不過還好，邏輯中的 && 有個神奇的特性， x && True 中，0 && True 剛好會是 False ，而前面說過任何非 0 數字都會當成 True。因此任何非 0 的 n && True 等同於 True && Ture，所以這個方法可以拿來過濾掉 0 這個特殊的狀況。

這樣講可能稍微有點不明白，那我稍微列個表來做為解說

n && !(n & n - 1)當中分別代表兩種狀況：

  1. 是否為零

  2. 是否為 2 的次方

     如果是 2 的次方：
 非 0 && True => True
 0 && True => False
 
 如果不是 2 的次方：
 非 0 && False => False
 0 && False => False

這個方法非常的妥善運用到 && 運算只要遇到一邊有 False 的狀況，結果一定就是 False

我真的覺得早期的人真的非常善用二進位數學的各種特性呀，真想好好的學習各種二進位的思考方式。