# 0342. 4 的幂
### 题目地址(342. 4 的幂)
### 题目描述
```
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
示例 1:
输入: 16
输出: true
示例 2:
输入: 5
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
```
### 前置知识
* 数论
### 公司
* 百度
* twosigma
### 思路
符合直觉的做法是不停除以 4 直到不能整除，然后判断是否为 1 即可。 代码如下：
```js
while (num && num % 4 == 0) {
num /= 4;
}
return num == 1;
```
但是这道题目有一个 follow up: “你是否可以不使用循环/递归完成”。因此我们需要换种思路。
我们先来看下，4 的幂次方用 2 进制表示是什么样的.
发现规律： 4 的幂次方的二进制表示 1 的位置都是在奇数位（且不在最低位），其他位置都为 0
我们还可以发现： 2 的幂次方的特点是最低位之外，其他位置有且仅有一个 1（1 可以在任意位置）
我们进一步分析，如果一个数字是四的幂次方，那么只需要满足：
1. 是 2 的幂次方， 就能保证最低位之外，其他位置有且仅有一个 1
2. 这个 1 不在偶数位置，一定在奇数位置
对于第一点，如果保证一个数字是 2 的幂次方呢？ 显然不能不停除以 2，看结果是否等于 1，这样就循环了。 我们可以使用一个 trick， 如果一个数字 n 是 2 的幂次方，那么 n & (n - 1) 一定等于 0， 这个可以作为思考题，大家思考一下。
对于第二点，我们可以取一个特殊数字，这个特殊数字，奇数位置都是 1，偶数位置都是 0，然后和这个特殊数字 `求与`， 如果等于本身，那么毫无疑问，这个 1 不再偶数位置，一定在奇数位置，因为如果在偶数位置，`求与`的结果就是 0 了 题目要求 n 是 32 位有符号整形，那么我们的特殊数字就应该是`01010101010101010101010101010101`(不用数了，一共 32 位)。
如上图，64 和这个特殊数字求与，得到的是本身。 8 是 2 的次方，但是不是 4 的次方，我们求与结果就是 0 了。
为了体现自己的逼格，我们可以使用计算器，来找一个逼格比较高的数字，这里我选了十六进制，结果是`0x55555555`。
代码见下方代码区。
说实话，这种做法不容易想到，其实还有一种方法。 如果一个数字是 4 的幂次方，那么只需要满足：
1. 是二的倍数
2. 减去 1 是三的倍数
代码如下：
```js
return num > 0 && (num & (num - 1)) === 0 && (num - 1) % 3 === 0;
```
### 关键点
* 数论
* 2 的幂次方特点（数学性质以及二进制表示）
* 4 的幂次方特点（数学性质以及二进制表示）
### 代码
语言支持：JS, Python
JavaScript Code：
```js
/*
* @lc app=leetcode id=342 lang=javascript
*
* [342] Power of Four
*/
/**
* @param {number} num
* @return {boolean}
*/
var isPowerOfFour = function (num) {
// tag: 数论
if (num === 1) return true;
if (num < 4) return false;
if ((num & (num - 1)) !== 0) return false;
return (num & 0x55555555) === num;
};
```
Python Code:
```python
class Solution:
def isPowerOfFour(self, num: int) -> bool:
if num == 1:
return True
elif num < 4:
return False
else:
if not num & (num-1) == 0:
return False
else:
return num & 0x55555555 == num
# 另一种解法：将数字转化为二进制表示的字符串，利用字符串的相关操作进行判断
def isPowerOfFour(self, num: int) -> bool:
binary_num = bin(num)[2:]
return binary_num.strip('0') == '1' and len(binary_num) % 2 == 1
```
**复杂度分析**
* 时间复杂度：$O(1)$
* 空间复杂度：$O(1)$
更多题解可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/342.power-of-four.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.