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``。函数没有需要修改的输入对象。 自建示例 -------- 零次幂边界: .. code-block:: text 输入:n = 1 输出:true 解释:存在整数 x=0,使 2^0=1。 正数但含多个二进制置位: .. code-block:: text 输入:n = 40 输出:false 解释:40 位于 32 和 64 之间,不等于任何一个 2 的整数次幂。 负数: .. code-block:: text 输入:n = -8 输出:false 解释:虽然绝对值 8 是二的幂,但 n 本身为负数,不符合等式 n=2^x。 二进制只有一个置位 ------------------ 正整数是 2 的整数次幂,当且仅当它的二进制表示只有一个 ``1``。对正数 ``n`` 计算 ``n-1`` 后,该唯一的最低位 ``1`` 会变成 ``0``,它右侧的 0 会变成 1;因此: .. code-block:: text 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++ 实现 -------- .. code-block:: cpp class Solution { public: bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } }; 代码分析 -------- 只进行一次比较和一次按位与,时间复杂度、额外空间均为 ``O(1)``。正数范围最多到 ``2^30``, 不会触及有符号 ``int`` 的负值边界;输入参数按值传递,不会被修改。