0231. Power of Two

题目信息

题号:

0231

难度:

Easy

主题:

数学、位运算、整数

原题:

LeetCode 0231

重点:

指数为整数、只有正数可能成立、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 的负值边界;输入参数按值传递,不会被修改。