CareerCup

Here.

bool isPowerof4(int i) {
    return ((i & 0xAAAAAAAA) == 0 && (i&(i-1)) == 0);
}

First check whether number is power of 2:

x = 2^k
x         == 0...010...0
x-1       == 0...001...1
x & (x-1) == 0...000...0

x != 2^k
x         == 0...1...010...0
x-1       == 0...1...001...1
x & (x-1) == 0...1...000...0

If it is not power of 2 - then it is not power of 4.
If it power of 2 - then it have exactly one 1 in binary record.

1   = 000000001 
4   = 000000100 
16  = 000010000 
64  = 001000000 
256 = 100000000

If it is power of 4 - position of this single 1 will be odd.

bool isPowerOfTwo = x && !(x & (x - 1));
//101010100 = 0x5...554
int mask = 0x5...554; //(or 0x5...555 is 1 should be included as 4^0) 
return isPowerOfTwo  && (x & mask );

Similar to joe_kidd's solution, the pattern we want to find is that there is exactly only one '1' in an odd position of the bit representation of the number.

Instead of looping and checking all possible numbers, which gives O(log n) runtime, we can do binary selection to further optimize it to O(log log n).

The idea is to break the number into 2 parts, and do zero-check on both parts. go to the part that is non-zero, until you find a '1' and check if its position is on an odd index. Go to the original number, flip the 1 on the index you found, and do zero-check of the flipped number.

PS: 1 is also counted as power of 4, I assume

Oh this one looked cool.
Write a multibyte example on paper, then you get the idea to use a lookup table:

Note: 4^i = (2^2)^i = 2^(2i)

Also, on paper you see that any integer is a power of 4 precisely when:
1) One of it's bytes is a power of 4
2) All other bytes are fully 0

bool LUT[1U<<8];  //look up: is a byte sized integer a power of 4?

//initialize: LUT[1U] = LUT[1U<<2] = LUT[1U<<4] = LUT[1U<<6] = true;

bool ispower4 ( uint x )
{
    union {
        uint whole;
        unsigned char part[sizeof(uint)];
    } var;

    bool bytecheck = false;   //whether we've seen a byte in the integer that's power of 4
    int zerobytes = 0;   //count number of all-0 bytes in integer
    int i;
    
    var.whole=x;
    for(i=0; i < sizeof(uint); i++)
    {
        if( LUT[var.part[i]] ) bytecheck=true;        //i-th byte is a power of 4
        else if (var.part[i] == 0x0 ) zerobytes++;  //i-th byte is all 0s
    }
           //all bytes are totally 0s, except 1 byte that is power of 4
    return ( zerobytes == sizeof(uint)-1 && bytecheck );

}

We list the following sequence:

a_0 = 4
a_1 = 4^{a_1}
a_2=4^{a_2}
...
a_n=4^{a_{n-1}}

We can find the range the integer N belongs to. say a_i, and a_{i+1}.

Now, do the previous calculation, and multiply a_i each time.

We recursively do the previous steps. Until we n=a^k or n is between a^k and a^k+1.

If it is important to do it in exactly O(lglgn):
Let's present x = y ^ k;
We can search this power k using binary search and use binary exponentiation for checking

-----------------------------------------------------------------------
The solution below fails for the case when the number is 12. Please take a look at Zoro post, as you get a correct solution there!!!
-----------------------------------------------------------------------

Take a look at the bit represantation of number that is power of 4 you get:

1 = 000000001
4 = 000000100
16 = 000010000
64 = 001000000
256 = 100000000
...
So the sum off all above gives us a mask
mask = (...)101010100 = 0x55554

So now we can write a function

bool isPowerOf4(int n)
{
int mask = 0x55554;
return !(n & ((n & mask) - 1));
}

Why does it work? Check what happens if n is a power of four:

for n = 16
n = 10000, mask = 10100
n & mask = 10000
(n & mask) - 1 = 01111
!(10000 & 01111) = !(0) == true

for n = 8
n = 01000, mask = 10100
n & mask = 00000
(n & mask) - 1 = 11111
!(01000 & 11111) = !(01000) = false

for n = 20
n = 10100, mask = 10100
n & mask = 10100
(n & mask) - 1 = 10111
!(10100 & 10111) = !(1000) == false


Regards Joe