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;某个数即使是二的幂,也只有指数为偶数时才是四的幂。进阶问题询问能否不使用循环或递归完成判断。

自建示例

较高次幂:

输入: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)。