Given a number which is power of 2, check if it is even power or odd power

math

I am given a number n , which is always a power of 2.
I want to check whether n is odd power of 2 or even power of 2.

For example: n=4 , ans= even
n=8, ans=odd (because 8 is 2^3)
n=1024 , ans=even.

Can I do it using bitwise operations/ or some faster method.

Best Answer

Lets start off with the statement 'bitwise operations on unbounded integers is meaningless'. You're not going to be testing if the number 2128 has an even exponent or not. The problem area is constrained to, lets say, unsigned 32 bits. This could also be 64 easily (the long data type), but its easier to type 32 bit numbers.

The number 2n, when written in binary has exactly one 1 in it:

20 = 0...0001
21 = 0...0010
22 = 0...0100
23 = 0...1000

and so forth. The question then is "what bitwise operation will have a value that is 0 or not 0 when done against such a number?"

The value would be 22 + 20 which gives us 5. This pattern repeats itself for all of the even exponents.

So, the bitwise operation is & 5 (or & A). The value of 52 is 0101 with the odd values as 0, while 102 is 1010 with the even values as 0. This value is then done for each nyble (half a byte) in the number: the value we are interested in is 0101 0101 0101 0101 0101 0101 0101 0101 or 0x55555555

n & 0x55555555 will give a value of 0 when the power of 2 is odd and some other value when the power of 2 is even. n & 0xAAAAAAAA will do the opposite (0 when the power of 2 is even and some other value when it is odd).

n & 0x55555555 is in effect n & (20 + 22 + 24 + 26 + ... + 230) which again, gives us the answer we are after.

Related Topic