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 not0
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 is0101
with the odd values as0
, while 102 is1010
with the even values as0
. This value is then done for each nyble (half a byte) in the number: the value we are interested in is0101 0101 0101 0101 0101 0101 0101 0101
or0x55555555
n & 0x55555555
will give a value of0
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.