342. 4的幂

题目

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

示例 1：

输入：n = 16
输出：true
示例 2：

输入：n = 5
输出：false
示例 3：

输入：n = 1
输出：true

提示：

-231 <= n <= 231 - 1

进阶：你能不使用循环或者递归来完成本题吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/power-of-four
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

2的幂比较好判断：二进制表示最高位为1，后面都是0，可以通过去掉最后一位1后判断是否等于0来判断。

一个数如果是4的幂，那么一定也是2的幂，但反过来不一定。因此，先基于上面2的幂的规则判断一下，如果不是2的幂那么可以直接返回false了。如果是，进行下一步判断：

4的幂和2的幂不同的地方在于，二进制表示时1一定在奇数位（从最低位开始数，并从1开始计数），那么可以判断这个1在奇数位还是偶数位来判断是否为4的幂。构造一个奇数位全是1的数（16进制表示下的0x55555555），如果和该数异或与之后不为0，那么说明是4的幂。

代码

class Solution {
    public boolean isPowerOfFour(int n) {
        if (n < 0) {
            return false;
        }
        return ((n & (n - 1)) == 0) && ((n & 0x55555555) != 0);
    }
}