iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 12
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 12

【從面試題學邏輯-12】如何確認是不是2的N次方(leetcode 231. Power of Two)

題目:
請寫一個方法檢查輸入的數字是否為2的n次方

舉例:
輸入1 → true (1 = 2的0次方)
輸入3 → false

點我前往LeetCode題目頁面


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


我們先上程式碼再做解釋

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & n-1) == 0;
    }
}

蛤?你說什麼?怎麼只有一行?/images/emoticon/emoticon04.gif

我們逐一看一下上面是什麼意思

n > 0

因為2的n次方一定是正的,所以一定要加這一段來避免負數問題/images/emoticon/emoticon28.gif

接下來

(n & n-1) === 0

這到底是什麼魔術?其實這段也有出現在CTCI的5.5喔!只是在CTCI是要解釋作用,那這段程式碼到底代表什麼呢?

這段代表的是找出2的n次方,它的原理是這樣,我們知道電腦儲存數字是二進位,如果2的話就是0010,3就是0011

所以只要是2的n次方,他的二進位一定是1個1後面加上多個0

  • 1 → 0001
  • 2 → 0010
  • 4 → 0100
  • 8 → 1000
  • 以此類推

(示範起見我們只show尾巴四位數)

那為何要和n-1做AND(&)呢?我們知道2的n次方是1個1後面加上多個0,而2的n次方-1,他的二進位就會是下面這種情況:

  • 8 → 1000
    7 → 0111
  • 4 → 0100
    3 → 0011

有沒有發現?-1就可以讓後面的0全部翻轉成1,而原本的那個1就會變成0,如果兩者做AND,我們就可以拿到0000的結果,所以這段程式碼就可以做到巧妙的確認是否是2的n次方!

當然,前面說到2的n次方,二進位內只有1個1,所以也可以用Integer.bitCount()來計算二進位內有幾個1。

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && Integer.bitCount(n) == 1;
    }
}

這段程式碼也可以得到一樣的效果

題目解決!


如果有時間我們也會談談Integer.bitCount()在做什麼

希望能夠順利講完/images/emoticon/emoticon16.gif


上一篇
【從面試題學邏輯-11】如何在一堆出現兩次的數中找到不重複的那位仁兄?(leetcode 136. Single Number)
下一篇
【從面試題學邏輯-13】你以為找次方結束了嗎?並沒有,還有4的n次方!(leetcode 342. Power of Four)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言