fastest way to find a given number 'n' can be absolutely expressed as 2^m [duplicate]
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 ?
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 2m 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.
精彩评论