未分類

Power of Two

BitManipulation, Go, LeetCode, Math

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。

分享到