iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 13
0
自我挑戰組

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

【從面試題學邏輯-13】你以為找次方結束了嗎?並沒有,還有4的n次方!(leetcode 342. Power of Four)

你以為Power of系列結束了嗎?/images/emoticon/emoticon01.gif

並沒有.png

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

舉例:
輸入16 → true (16 = 4的2次方)
輸入8 → false

點我前往LeetCode題目頁面


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

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


本題是昨日題目的進階題,請先讀過昨天的文章再往下閱讀喔

讓我們先上程式碼再做解釋

class Solution {
    public boolean isPowerOfFour(int num) 
    {
        return num>0 && (num&(num-1)) == 0 && (num&0x55555555) != 0;
    }
}

又是一行!?/images/emoticon/emoticon06.gif

num>0 && (num&(num-1)) == 0

昨天我們解釋了上面這個東西,它就是用來找2的n次方用的

(num&0x55555555) != 0

那這位仁兄你又是哪位!?

讓我們逐一解釋下去

0x55555555

這個東西代表的是一串16進位的數字,那它具體而言是幹嘛用的?

我們上一張計算機轉換的圖片,HEX是16進位、DEC是10進位、OCT是8進位,而最後的BIN就是2進位

大家一定會好奇:
這個二進位怎麼是0101一直下去??

這裡要先幫明天的題目起個頭,這一串0101是用來當Mask(遮罩)用的喔!

不知道Mask的話我們舉個例子,大家應該喝過有鮮奶油或奶泡的飲品吧?上面有時候會撒上有形狀的可可粉、咖啡粉。而要撒這種形狀的粉,就要有一個特殊形狀的模具擋住不要的部分。Mask就是為了在位元運算中,幫我們擋掉不要的位元用的那個特殊模具。

(num&0x55555555)

所以上面這個情況下,我們用num0x55555555這個特殊模具做AND,就可以把偶數位數的位元給刪掉!(位數由右數到左)

1111
0101
-----
0101

像是上面一樣

我們知道前面那段程式碼是2的n次方,但2的n次方不見得是4的n次方,但仔細想想,2的n次方是二進位中只有1個1,4的n次方其實等於2的2n次方,也是1個1,只不過這個1在奇數位啊!

第一位數代表的是2的0次方
第三位數代表的是2的2次方
第五位數代表的是2的4次方

找到規律啦!/images/emoticon/emoticon07.gif

總和以上,如果num用Mask把偶數位數刪掉後不為零,代表說它就是4的n次方

解決!


今天我們幫Mask開個頭,明天會來一題真的要用Mask做的題目喔


上一篇
【從面試題學邏輯-12】如何確認是不是2的N次方(leetcode 231. Power of Two)
下一篇
【從面試題學邏輯-14】你看過灑可可粉,那你看過撒0和1嗎?(CTCI 5.1 在二進位中插入另一個二進位)
系列文
新手也能學!一起從面試題理解程式邏輯!30

1 則留言

1
神威
iT邦研究生 5 級 ‧ 2020-09-26 10:43:54

看到大大解題,也分享一下我這題的解法

class Solution {
    public boolean isPowerOfFour(int n) {
          
        return n > 0 && (n & n-1)==0 && Integer.numberOfLeadingZeros(n)%2!=0; 
    }
}

我要留言

立即登入留言