342. 4的幂

Easy

题目描述

给定一个整数 n，如果它是 4 的幂次方，则返回 true；否则，返回 false。

如果存在一个整数 x 使得 n == 4^x，则认为 n 是 4 的幂次方。

示例 1：

输入：n = 16
输出：true

示例 2：

输入：n = 5
输出：false

示例 3：

输入：n = 1
输出：true

约束条件：

进阶： 你能不使用循环或者递归来解决这个问题吗？

这道题要判断一个数是否为 4 的幂次方，有三种常见的解法：

解法一：暴力法
通过循环不断除以 4，如果最终结果为 1 则是 4 的幂次方。需要注意处理负数和 0 的情况。

解法二：递归法
利用递归的思想，如果 n % 4 == 0，则递归检查 n / 4，递归终止条件是 n == 1。

解法三：位运算法（最优）
4 的幂次方有特殊的二进制模式：

位运算解法的核心思想：4 的幂次方 = 2^(2k)，即指数必须是偶数。在二进制表示中，这意味着唯一的 1 位必须在偶数位置。

推荐使用位运算解法，因为它时间复杂度为 O(1)，且符合进阶要求。

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
    }
};

class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0

public class Solution {
    public bool IsPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
    }
}

var isPowerOfFour = function(n) {
    return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
};