一個二進位方法判斷是否為 2 的次方數

今天看了一個問題,是叫你寫個程式判斷一個數字 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

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