未分類

Power of Two

Power of Two

Given an integer, write a function to determine if it is a power of two.

提示 解題應用
Math 規律觀查
BitManipulation AND

Default:

1
2
3
func isPowerOfTwo(n int) bool {
}

解答思路:

一開始對BitManipulation思索半天,唯一能確定的是如果是在二進位中,要符合二的n次方肯定第一個位元是1而且只有1個,至於後面有多少個0就看次方是多少,但如果我們是以這樣的來方判斷是不是二進位只有一個1,意味著要遍歷每一個位元,這樣需要的時間其實就和我們將值不斷除以2來確認餘數是否為0差不多:

1
2
3
4
5
6
7
8
9
10
11
12
func isPowerOfTwo(n int) bool {
if n <= 0 {
return false
}
for n != 1 {
if n%2 != 0 {
return false
}
n = n / 2
}
return true
}

至於在確認完其它人對BitManipulation解法後恍然大悟,只要將該數與該數-1兩個值做AND便能輕易的判斷,因為如果是二的n次方在二進位中是必開頭位元為1其餘位元為0,此時如果將該值-1就會變成開頭位元為0其餘位元為1,如果將兩個值做AND就可以知道為0的結果勢必為2的n次方,因為1與0做AND為0,其餘的狀況則非為2的n次方值。

程式碼解說:

一開始要先判斷該數是不是為0或為負數,因為0與負數肯定不是2的n次方值,接著我們才確認如上述所說的(該數)與(該數-1)做二進位的&(AND),如果結果為0就回傳true,否則回傳false

1
2
3
4
if n > 0 && n&(n-1) == 0 {
return true
}
return false

完整程式碼:

1
2
3
4
5
6
func isPowerOfTwo(n int) bool {
if n > 0 && n&(n-1) == 0 {
return true
}
return false
}

總結:

要確認一數是否為2的n次方有兩種方法,其一是將該數不斷除以2來確認餘數是否為0直到值為1,另一種方是則是將(該數)與(該數-1)做二進位的&(AND),若為二的n次方其結果必為0。

分享到