原题链接在这里：

题目：

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:

Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

题解：

与, 类似。

每次iteration若是不能被4整除即return false. 若可以被4整除，便除以4, 直到结果等于1.

Time Complexity: O(log(num)). Space: O(1).

AC Java:

1 public class Solution { 2     public boolean isPowerOfFour(int num) { 3         if(num<=0){ 4             return false; 5         } 6         while(num%4 == 0){ 7             num /= 4; 8         } 9         return num==1;10     }11 }

Follow up 需要no loops/recursion.

可以bit manipulation, 首先判定num是否为2的幂数. 若是2的幂数, num二进制表达首位为1, num-1除首位均为1. num & num-1 应等于 0.

然后判定首位的1是在奇数位置上, eg. 10000 = 16. 所以 num & 0x55555555 应等于num 原值.

Time Complexity: O(1). Space: O(1).

1 public class Solution {2     public boolean isPowerOfFour(int num) {3         return num>0 && (num & num-1) == 0 && (num & 0x55555555) == num;4     }5 }