未分類

Power of Four

BitManipulation, Go, LeetCode

Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

For Example:

1
Given num = 16, return true. Given num = 5, return false.

Follow up:

Could you solve it without loops/recursion?

提示 解題應用
BitManipulation 二進位長度

Default:

1
2
3
func isPowerOfFour(num int) bool {
}

解答思路:

先前曾經寫過類似的題目Power of Two，當然還有Power of Three，這次則是Power of Four，當然在想的時候會發現你在確認4的n次方同時，其值很可能也是2的n次方，畢竟4的n次方同時也是2的2n次方，所以倒不如直接用2的n次方尋找方式去篩選，而如果將值轉成二進位更可以發現到4的n次方二進位長度都為奇數，2的n次方則為偶數如下:

2 10 長度:2
4 100 長度:3
8 1000 長度:4
16 10000 長度:5

因此找出其為2次方的同時，再利用長度篩出是否為4次方即可達到目地。

程式碼解說:

如之前找2的n次方程式碼差不多，該值與該值-1做AND，而這次為了要確認是否為4的n次方，多了一個二進位的長度判斷，這邊用上了strconv的library，將其值轉為二進位字串，接著再開始判斷長度是否為奇數，若長度為奇數又是二的n次方，其值必為4的n次方回傳，其餘2的n次方不為4的n次方或連2的n次方都不是的狀況則回傳false

1
2
3
4
5
binary := strconv.FormatInt(int64(num), 2)
if num > 0 && len(binary)%2 != 0 && num&(num-1) == 0 {
	return true
}
return false

完整程式碼:

1
2
3
4
5
6
7
func isPowerOfFour(num int) bool {
	binary := strconv.FormatInt(int64(num), 2)
	if num > 0 && len(binary)%2 != 0 && num&(num-1) == 0 {
		return true
	}
	return false
}

總結:

要確認某值是否為4的n次方，換句話說其值也是2的2n次方，所以倒不如直接用2的n次方尋找方式去篩選，而將值轉成二進位更可以發現到4的n次方二進位長度都為奇數，2的n次方則為偶數，因此再確認其為2的n次方值的同時，再利用長度篩出是否為4的n次方即可達到目地。

分享到