0231. Power of Two¶
题目信息¶
- 题号:
0231
- 难度:
Easy
- 主题:
数学、位运算、整数
- 原题:
- 重点:
指数为整数、只有正数可能成立、1 等于 2 的零次幂、32 位边界
题目重述¶
给定一个 32 位有符号整数 n,判断是否存在某个整数 x,使 n == 2^x。满足条件时返回 true,否则返回 false。
n 位于 [-2^31, 2^31-1]。由于二的整数次幂在本题语义下必须是正整数,所以 0 和所有负数都返回 false;1 等于 2^0,因此返回 true。函数没有需要修改的输入对象。
自建示例¶
零次幂边界:
输入:n = 1
输出:true
解释:存在整数 x=0,使 2^0=1。
正数但含多个二进制置位:
输入:n = 40
输出:false
解释:40 位于 32 和 64 之间,不等于任何一个 2 的整数次幂。
负数:
输入:n = -8
输出:false
解释:虽然绝对值 8 是二的幂,但 n 本身为负数,不符合等式 n=2^x。
二进制只有一个置位¶
正整数是 2 的整数次幂,当且仅当它的二进制表示只有一个 1。对正数 n 计算
n-1 后,该唯一的最低位 1 会变成 0,它右侧的 0 会变成 1;因此:
n = 1000...000
n - 1 = 0111...111
n & (n-1) = 0
若 n 至少有两个置位,清除最低置位后仍会留下其他 1,结果不为 0。先判断 n>0,
既排除 0 和负数,也避免在有符号整数的负数表示上使用不必要的位运算。
正确性说明¶
n=1 时 n-1=0,对应 2^0;任意正的二次幂只有一个二进制置位,按上述性质通过检查。
非二次幂的正数至少有两个置位,n & (n-1) 保留较高置位而不为 0;非正数在第一项检查处被拒绝,
所以判断条件是充要的。
C++ 实现¶
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};
代码分析¶
只进行一次比较和一次按位与,时间复杂度、额外空间均为 O(1)。正数范围最多到 2^30,
不会触及有符号 int 的负值边界;输入参数按值传递,不会被修改。