快速判斷N是否為2的次方數

前陣子遇到一個題目 : 請你判斷一個正整數N是否為2的次方。

 

我遇到這題目時,直覺想到的就是,透過迴圈從1開始檢查所有2的次方數,像這樣 :

雖然這樣就解決了,但我一直在想是否有效率更高的方法。

 

我們先來觀察2的次方數轉成2進制的樣子 :

1        =>        0000  0001    ,    1 – 1        =>        0000  0000

2        =>        0000  0010    ,    2 – 1        =>        0000  0001

4        =>        0000  0100    ,    4 – 1        =>        0000  0011

8        =>        0000  1000    ,    8 – 1        =>        0000  0111

16     =>        0001  0000    ,    16 – 1      =>        0000  1111

32     =>        0010  0000    ,    32 – 1      =>        0001  1111

可以發現,只要該數是2的次方時,除了MSB(最高位元)是 1 其餘都是0,

然後我們又可以發現,2的次方數減1後,剛好等於原數NOT後的值。

 

在數位邏輯中 N & !N = 0,我們可以透過這個方法來判斷N是否為2的次方,所以是否為2的次方的判斷規則就是 N & (N-1) == 0

在數學中規定0不是任何人的次方,但這裡會有個小問題,當我們把0帶入後照樣會得到true,因為0不管和誰做AND都是0,所以要再加上一個 n > 0來塞選。

 

最後我們得到一行簡短的判斷式

 

那為什麼只要 n & n-1 == 0就代表是2的次方數呢?

根據上面列出的幾個數字,得出如果該數是2的次方數,就只有MSB為1,而其餘數字都會有2個以上的1,所以在減1時,就不會跟MSB借位,也就沒辦法達到NOT的效果。

7 = 0111,  7 – 1 = 0110   =>   7 & (7-1) =  110,    110 != 0

沒辦法達到NOT效果的話,在做AND運算時就不會得到0,只有在該數為2的次方數時,AND後才會是零,所以我們能透過 n & n-1 == 0 來判斷 N 是否為2的次方數

 

 

如有錯誤請指證