Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
給定一個(gè)32位的整數(shù)，判斷是否為4次冪

　　一開始看到這題我就想到打表，但是，果然還是位運(yùn)算最厲害

Example:

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

Follow up

Could you solve it without loops/recursion?

My Solution

(Java) Version 1 Time: 2ms:

　　沒有什么好說的，在32位數(shù)的世界里面，4次冪并沒有幾個(gè)，只有15個(gè)數(shù)，直接存數(shù)組里面對(duì)比就是了，只是沒有想到還是慢了

public class Solution {
    public boolean isPowerOfFour(int num) {
        int[] integer = new int[]{1,4,16,64,256,1024,4096,16384,65536,262144,1048576,4194304,16777216,67108864,268435456,1073741824};
        for(int i=0;i<16;i++){
            if(num==integer[i])return true;
        }
        return false;
    }
}

(Java) Version 2 Time: 3ms (By k'):

　　不僅簡(jiǎn)潔還快，果然所有和2次冪扯上關(guān)系的，都可以讓位運(yùn)算來一腳

　　老外的解釋：
　　The mask is 01010101010101010101010101010101 (0x55555555), reason for that is any number that is power of 4 happens bit and other bit.

　　For example for 8 bits:
　　4 ^ 0 = 00000001 (first bit is set)
　　4 ^ 1 = 00000100 ( third bit is set)
　　4 ^ 2 = 00010000 (5th bit is set)
　　and so on

　　So the mask would be 0x55555555 (this will take care of the sign bit too)
　　The other part is that you want to make sure that only one bit is set in the number (similar to numbers of power 2), this is done by num == (num & -num)
　　num == (num & -num) will return true only if there was one bit set, the reason has to do about 2's complement representation.

　　For example:
　　4 = 00000100
　　-4 = 11111011 + 1 = 11111100
　　so 00000100 & 11111100 = 00000100

　　The only exception for this rule is if num is 0 which explains why we check num != 0
　　This solution would work for any number that is power of 2 (4, 8, 16, ..), you just need to adjust the mask

public class Solution {
    public boolean isPowerOfFour(int num) {
        return num != 0 && (num & 0x55555555) == num && num == (num & -num);
    }
}

(Java) Version 3 Time: 21ms (By yfcheng):

　　有意思的從字符串出發(fā)的思路，雖然慢就慢了點(diǎn)
　　老外的解釋：

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 class Solution {
    public boolean isPowerOfFour(int num) {
        return Integer.toString(num, 4).matches("10*");
    }
}

(Java) Version 4 Time: ms (By LeeLom):

　　似乎是一個(gè)通用的解法？

public class Solution { 
    public boolean isPowerOfFour(int num) { 
        int x = (int)Math.sqrt(num); 
        //1073741824 is 4^15, 4^16 is bigger than int  
        return(num > 0 && 1073741824 % num == 0 && x*x == num); 
    }
}