342. Power of Four

题目

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

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

题目大意

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

解题思路

• 判断一个数是不是 4 的 n 次方。
• 这一题最简单的思路是循环，可以通过。但是题目要求不循环就要判断，这就需要用到数论的知识了。
• 证明 (4^n - 1) % 3 == 0，(1) 4^n - 1 = (2^n + 1) * (2^n - 1)(2) 在任何连续的 3 个数中 (2^n-1)，(2^n)，(2^n+1)，一定有一个数是 3 的倍数。(2^n) 肯定不是 3 的倍数，那么 (2^n-1) 或者 (2^n+1) 中一定有一个是 3 的倍数。所以 4^n-1 一定是 3 的倍数。

代码

package leetcode

// 解法一 数论
func isPowerOfFour(num int) bool {
	return num > 0 && (num&(num-1)) == 0 && (num-1)%3 == 0
}

// 解法二 循环
func isPowerOfFour1(num int) bool {
	for num >= 4 {
		if num%4 == 0 {
			num = num / 4
		} else {
			return false
		}
	}
	return num == 1
}