## Monday, April 18, 2016

### LeetCode 342 - Power of Four

https://www.hrwhisper.me/leetcode-power-four/
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?

https://segmentfault.com/a/1190000003481153

### 思路

``````1   0 0000 0001
4   0 0000 0100
16  0 0001 0000
64  0 0100 0000
256 1 0000 0000``````

``````private boolean bruteForceBit(long num){
boolean res = false;
if(num <= 0) return res;
for(int i = 1; i <= 64; i++){
// 如果该位是0，则不操作
if((num & 1) == 1){
// 如果是偶数位为1，说明不是4的幂
if(i % 2 == 0) return false;
// 如果是奇数位为1，如果之前已经有1了，则也不是4的幂
if(res){
return false;
} else {
// 如果是第一次出现技术位为1，则可能是4的幂
res = true;
}
}
num = num >>> 1;
}
return res;
}``````
http://www.programcreek.com/2015/04/leetcode-power-of-four-java/
 ```public boolean isPowerOfFour(int num) { int count0=0; int count1=0;   while(num>0){ if((num&1)==1){ count1++; }else{ count0++; } num>>=1; }   return count1==1 && (count0%2==0); }```

power of two的时候，我们用 n &(n-1) ==0 来判断是否是2的次方数，这里也先判断一下是否为2的次方数。然后再把不是4的次方数排除掉，比如8.

So，如果我们与上一个可以在奇数上面选择位置的数，也就是 0101 0101 ……那么就把不是4次方的排除掉啦
0101 0101 …… 十六进制表示为： 0x55555555
``````private boolean smartBit(long num){
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x5555555555555555l) == num);
}``````
public boolean isPowerOfFour(int num) {
return num > 0 && (num & (num - 1)) ==0  && (num & 0x55555555) !=0;
}

https://leetcode.com/discuss/97930/java-1-line-cheating-for-the-purpose-of-not-using-loops
``````public boolean isPowerOfFour(int num) {
return (Math.log(num) / Math.log(4)) % 1 == 0;
}
```

```

``````    public boolean isPowerOfFour(int num) {
return num > 0 && (num&(num-1)) == 0 && (num & 0x55555555) != 0;
//0x55555555 is to get rid of those power of 2 but not power of 4
//so that the single 1 bit always appears at the odd position
}
``````
http://www.cnblogs.com/grandyang/p/5403783.html

```    bool isPowerOfFour(int num) {
return num > 0 && !(num & (num - 1)) && (num & 0x55555555) == num;
}```

```    bool isPowerOfFour(int num) {
return num > 0 && !(num & (num - 1)) && (num - 1) % 3 == 0;
}
```

The idea is that numbers in quaternary system that is power of 4 will be like 10, 100, 1000 and such. Similar to binary case. And this can be extended to any radix.
``````public boolean isPowerOfFour(int num) {
return Integer.toString(num, 4).matches("10*");
}``````
https://leetcode.com/discuss/97926/java-line-solution-using-bitcount-numberoftrailingzeros
``````public boolean isPowerOfFour(int num) {
return num>=1 && Integer.bitCount(num) == 1 && Integer.numberOfTrailingZeros(num)%2 == 0;
}
```

```

``````private boolean bruteForceMod(long num){
if(num <= 0) return false;
while(num % 4 == 0){
num = num / 4;
}
return num == 1;
}``````
http://www.cnblogs.com/grandyang/p/5403783.html
```    bool isPowerOfFour(int num) {
return num > 0 && int(log10(num) / log10(4)) - log10(num) / log10(4) == 0;
}```
http://www.programcreek.com/2015/04/leetcode-power-of-four-java/
We can use the following formula to solve this problem without using recursion/iteration.
``` public boolean isPowerOfFour(int num) { if(num==0) return false;   int pow = (int) (Math.log(num) / Math.log(4)); if(num==Math.pow(4, pow)){ return true; }else{ return false; } } ```