342. 4的幂

# 题目

## 342. 4 的幂

[https://leetcode-cn.com/problems/power-of-four/](https://leetcode-cn.com/problems/power-of-four/)

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

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

**示例 1：**

```
输入：n = 16
输出：true
```

**示例 2：**

```
输入：n = 5
输出：false
```

**示例 3：**

```
输入：n = 1
输出：true
```

**提示：**

- `-231 <= n <= 231 - 1`

**进阶：**

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

# 题解

## 思路

## 代码

```javascript
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function(n) {
    return n > 0 && (n & (n - 1)) === 0 && (n & 0xaaaaaaaa) === 0;
};
```

## 官方

### 题目解析

这道题最直接的方法就是不停的去除以 4 ，看最终结果是否为 1 ，参见代码如下：

```
class Solution {
    public boolean isPowerOfFour(int num) {
         while ( (num != 0)  && (num % 4 == 0)) {
            num /= 4;
        }
        return num == 1;
    }
}
```

不过这段代码使用了 **循环** ，逼格不够高。

对于一个整数而言，如果这个数是 4 的幂次方，那它必定也是 2 的幂次方。

我们先将 2 的幂次方列出来找一下其中哪些数是 4 的幂次方。

| 十进制 | 二进制                          |
| ------ | ------------------------------- |
| 2      | 10                              |
| 4      | **100** （1 在第 3 位）         |
| 8      | 1000                            |
| 16     | **10000**（1 在第 5 位）        |
| 32     | 100000                          |
| 64     | **1000000**（1 在第 7 位）      |
| 128    | 10000000                        |
| 256    | **100000000**（1 在第 9 位）    |
| 512    | 1000000000                      |
| 1024   | **10000000000**（1 在第 11 位） |

找一下规律： 4 的幂次方的数的二进制表示 1 的位置都是在**奇数位**。

之前在小吴的文章中判断一个是是否是 2 的幂次方数使用的是位运算 `n & ( n - 1 )`。同样的，这里依旧可以使用位运算：将这个数与特殊的数做位运算。

这个特殊的数有如下特点：

- 足够大，但不能超过 32 位，即最大为 1111111111111111111111111111111（ 31 个 1）
- 它的二进制表示中奇数位为 1 ，偶数位为 0
  
  符合这两个条件的二进制数是：

```
1010101010101010101010101010101
```

**如果用一个 4 的幂次方数和它做与运算，得到的还是 4 的幂次方数**。

将这个二进制数转换成 16 进制表示：0x55555555 。有没有感觉逼格更高点。。。

![img](/media/202105/2021-05-31_231827.png)

### 图片描述

![img](/media/202105/2021-05-31_231827.png)

```java
class Solution {
    public boolean isPowerOfFour(int num) {
        if (num <= 0)
			return false;
        //先判断是否是 2 的幂
		if ((num & num - 1) != 0)
			return false;
        //如果与运算之后是本身则是 4 的幂
		if ((num & 0x55555555) == num)
			return true;
		return false;
    }
}
```