evaluate whether a number is integer power of 4

Question

The following function is claimed to evaluate whether a number is integer power of 4. I do not quite understand how it works?

bool fn(unsigned int x)
{
if ( x == 0 ) return false;
if ( x & (x - 1) ) return false;
return x & 0x55555555;
}

Answer 1

The first condition rules out 0, which is obviously not a power of 4 but would incorrectly pass the following two tests. (EDIT: No, it wouldn't, as pointed out. The first test is redundant.)

The next one is a nice trick: It returns true if and only if the number is a power of 2. A power of two is characterized by having only one bit set. A number with one bit set minus one results in a number with all bits previous to that bit being set (i.e. 0x1000 minus one is 0x0111). AND those two numbers, and you get 0. In any other case (i.e. not power of 2), there will be at least one bit that overlaps.

So at this point, we know it's a power of 2.

x & 0x55555555 return non-zero (=true) if any even bit it set (bit 0, bit 2, bit 4, bit 6, etc). That means it's power of 4. (i.e. 2 doesn't pass, but 4 passes, 8 doesn't pass, 16 passes, etc).

Answer 2

Every power of 4 must be in the form of 1 followed by an even number of zeros (binary representation): 100...00:

100 = 4

10000 = 16

1000000 = 64

1. The 1st test ("if") is obvious.

2. When subtracting 1 from a number of the form XY100...00 you get XY011...11. So, the 2nd test checks whether there is more than one "1" bit in the number (XY in this example).

3. The last test checks whether this single "1" is in the correct position, i.e, bit #2,4,6 etc. If it is not, the masking (&) will return a nonzero result.