forked from MisterBooo/LeetCodeAnimation
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0342-Power-Of-Four.md
112 lines (77 loc) · 3.03 KB
/
0342-Power-Of-Four.md
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
# LeetCode 第 342 号问题：4 的幂
> 本文首发于公众号「图解面试算法」，是 [图解 LeetCode ](<https://github.com/MisterBooo/LeetCodeAnimation>) 系列文章之一。
>
> 同步博客：https://www.algomooc.com
题目来源于 LeetCode 上第 342 号问题：4 的幂。题目难度为 Easy，目前通过率为 45.3% 。
### 题目描述
给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
**示例 1:**
```
输入: 16
输出: true
```
**示例 2:**
```
输入: 5
输出: false
```
**进阶：**
你能不使用循环或者递归来完成本题吗？
### 题目解析
这道题最直接的方法就是不停的去除以 4 ，看最终结果是否为 1 ，参见代码如下：
```java
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
符合这两个条件的二进制数是：
```java
1010101010101010101010101010101
```
**如果用一个 4 的幂次方数和它做与运算，得到的还是 4 的幂次方数**。
将这个二进制数转换成 16 进制表示：0x55555555 。有没有感觉逼格更高点。。。
### 图片描述
### 代码实现
```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;
}
}
```
