0342. Power of Four =================== 题目信息 -------- :题号: 0342 :难度: Easy :主题: 整数、幂、指数、正数边界 :原题: `LeetCode 0342 `_ :重点: 指数必须是整数、``4^0`` 等于 1、二的幂不一定是四的幂、非正数均不满足 题目重述 -------- 给定 32 位有符号整数 ``n``,判断是否存在整数 ``x`` 使 ``n = 4^x``。四的整数次幂始终为正数,因此零和负数不能满足条件。 ``n`` 位于 ``[-2^31, 2^31-1]``。指数可以为 ``0``,所以 ``1 = 4^0`` 应返回 ``true``;某个数即使是二的幂,也只有指数为偶数时才是四的幂。进阶问题询问能否不使用循环或递归完成判断。 自建示例 -------- 较高次幂: .. code-block:: text 输入:n = 256 输出:true 解释:256 = 4^4。 是二的幂但不是四的幂: .. code-block:: text 输入:n = 8 输出:false 解释:8 = 2^3,不存在整数 x 使 4^x=8。 指数为零: .. code-block:: text 输入: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++ 实现 -------- .. code-block:: cpp class Solution { public: bool isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0; } }; 代码分析 -------- ``n & (n - 1)`` 在且仅在 ``n`` 为二的幂时为零,掩码再排除奇数指数的二的幂;两个条件结合才对应四的幂。算法不循环、不递归,时间和额外空间均为 ``O(1)``。