額，又是一道裝逼解法的算法題

題目來源於 LeetCode 上第 342 號問題：4 的冪。題目難度為 Easy，目前通過率為 45.3% 。

題目描述

給定一個整數 (32 位有符號整數)，請編寫一個函數來判斷它是否是 4 的冪次方。

示例 1:

輸入: 16
輸出: true

示例 2:

輸入: 5
輸出: false

進階：你能不使用循環或者遞歸來完成本題嗎？

題目解析

這道題最直接的方法就是不停的去除以 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 。有沒有感覺逼格更高點。。。

圖片描述

代碼實現

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;
 }
}