0342. Power of Four¶
题目信息¶
- 题号:
0342
- 难度:
Easy
- 主题:
整数、幂、指数、正数边界
- 原题:
- 重点:
指数必须是整数、
4^0等于 1、二的幂不一定是四的幂、非正数均不满足
题目重述¶
给定 32 位有符号整数 n,判断是否存在整数 x 使 n = 4^x。四的整数次幂始终为正数,因此零和负数不能满足条件。
n 位于 [-2^31, 2^31-1]。指数可以为 0,所以 1 = 4^0 应返回 true;某个数即使是二的幂,也只有指数为偶数时才是四的幂。进阶问题询问能否不使用循环或递归完成判断。
自建示例¶
较高次幂:
输入:n = 256
输出:true
解释:256 = 4^4。
是二的幂但不是四的幂:
输入:n = 8
输出:false
解释:8 = 2^3,不存在整数 x 使 4^x=8。
指数为零:
输入:n = 1
输出:true
解释:1 = 4^0。
二的幂再加上指数奇偶性¶
4^x = 2^(2x),所以四的幂首先必须是正的二的幂:二进制中只能有一个 1。仅有这一条件还不够,例如 8 = 2^3 不是四的幂;还要保证这个唯一的 1 位出现在偶数位置(从最低位位置 0 开始)。
掩码 0x55555555 的二进制 1 恰好位于 0、2、4、…… 等偶数位置。先用 n & (n - 1) 检查单个置位,再与掩码相交即可;正数检查排除零和负数,1 的最低位符合掩码并代表 4^0。
C++ 实现¶
class Solution {
public:
bool isPowerOfFour(int n) {
return n > 0
&& (n & (n - 1)) == 0
&& (n & 0x55555555) != 0;
}
};
代码分析¶
n & (n - 1) 在且仅在 n 为二的幂时为零,掩码再排除奇数指数的二的幂;两个条件结合才对应四的幂。算法不循环、不递归,时间和额外空间均为 O(1)。