fastest way to find a given number 'n' can be absolutely expressed as 2^m

Question

Possible Duplicate:
How to check if a number is a power of 2

fastest way to find a given number 'n' can be expressed as 2^m

ex: 16= 2^4

naive solution: divide given number by 2 until the remainder becomes 0 (if successful) or less than two (if not successful)

Can someone tell me whats the other fastest way to compute this ?

thanks ram

Answer 1

Fastest way:

if (n != 0 && (n & (n - 1)) == 0)

If the number is a power of two, it will be represented in binary as 1 followed by m zeroes. After subtracting 1, it will be just m ones. For example, take m=4 (n=16)

10000 binary = 16 decimal
01111 binary = 15 decimal

Perform a bitwise "and" and you'll get 0. So it gives the right result in that case.

Now suppose that n is not exactly 2^m for some m. Then subtracting one from it won't affect the top bit... so when you "and" together n and n-1 the top bit will still be set, so the result won't be 0. So there are no false positives either.

EDIT: I originally didn't have the n != 0 test... if n is zero, then n & anything will be zero, hence you get a false positive.