快速判斷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的結果才會是零,最後就能透過結果是否為0來判斷N是不是2的次方數了

 

 

如有錯誤請指證