Find out if a number is a power of 2 using Bitwise Operators [O(1)]

Question

Hey I have a quick question:

How do I find out if an int is a power of 2 (only 1 positive bit) using bit-wise operators, in O(1) without any IF statements or any other type of BOOLEAN expression?

The method needs to return an integer value.

The method can return a certain number that you can decide on that means its a power of 2 and another number that means its not a power of 2. [Saying negative number means X and positive means Y is also allowed]

Also you can not rely on the fact that an int has 32 bits.

This is a question I was asked in an interview.

* A hint I was given was it had something to do with addition.. — Amit Assaraf, Jul 31 '14 at 16:05
"only 1 positive bit" is otherwise known as "is a *power* of 2" (not a factor) — harold, Jul 31 '14 at 16:05
possible duplicate of [How to check if a number is a power of 2](http://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2) — harold, Jul 31 '14 at 16:06
@harold Yeah sorry, I am not a native English speaker and I was struggling to find the word I was looking for which in this case was "power" — Amit Assaraf, Jul 31 '14 at 16:06
That's ok, you fixed it and you're still getting your answer, so everyone is happy (I hope) — harold, Jul 31 '14 at 16:07
@harold Not a duplicate as you cannot use IF statements, not even shortcut-ed ones. — Amit Assaraf, Jul 31 '14 at 16:07
This is also a duplicate of [the OP's previous question](http://stackoverflow.com/questions/24764512/check-for-only-one-positive-bit-in-a-type-of-java-in-o1). — Paul R, Jul 31 '14 at 16:08
@PaulR The question in the post was different and it was put on hold, I attempted to save posting another question by editing it and putting the new question there. But it wasn't answered because it was on hold. Check the edit history. — Amit Assaraf, Jul 31 '14 at 16:10
@harold You can not use any type of boolean expression, not IFs not == nothing, the method returns an integer value. Thus the question you posted as a duplicate doesn't apply to this question — Amit Assaraf, Jul 31 '14 at 16:11
You should fix your original question and get it re-opened rather than posting a duplicate. Also note that there are many other duplicates including the one @harold linked to above - please try searching before posting in future. — Paul R, Jul 31 '14 at 16:12
@PaulR as I stated before, this question has a twist that the other posts don't include in it that changes the answer thus I created a new post for it. — Amit Assaraf, Jul 31 '14 at 16:14
You haven't included this "twist" in your question - it just says: "using bit-wise operators, in O(1) without any IF statements". Please update the question if this is not what you are looking for, otherwise it's still a duplicate. — Paul R, Jul 31 '14 at 16:16
OK - it's easy to get the answer from one of the dupes though, e.g. you can just use `x & (x - 1)`, which gives 0 for power of 2, and >0 otherwise. — Paul R, Jul 31 '14 at 16:26
why not a duplicate? The answers in the other question doesn't use any if — phuclv, Apr 20 '16 at 03:15

score 5 · Accepted Answer · answered Aug 05 '14 at 09:10

If subtraction is acceptable then you can just use x & (x - 1), which gives 0 for power of 2, and >0 otherwise. If it needs to be a purely bitwise solution then you would need to implement the - 1 With bitwise operators in the usual way for two's complement arithmetic.

Find out if a number is a power of 2 using Bitwise Operators [O(1)]

1 Answers1