How do you find out if an unsigned integer is a power of 2

Question: How do you find out if an unsigned integer is a power of 2?


Answer: The trick here is to know that an unsigned integer which is a power of 2 has only one of its bits as 1. So a simple solution would be to loop through the bits and count the number of 1s.
There is another solution which uses bit manipulation.
isPower = (x !=0 && !(x & (x-1)))
x & (x-1) will always give you a 0 if x is a power of 2. !(x & (x-1)) should give us what we want but there is one corner case. If x is 0, then the second term alone would return true when the answer should be false. We need the check to make sure x is not 0.
Most interviewers would be happy with the first solution. The second solution might be quite hard to come up with on the spot unless of course you are a genius or you have read the solution before.

No comments:

 
Top Blogs