Mark As Completed Discussion

Check if a positive integer is a power of 2 without branching

In binary representation of any power of (decimal) 2, one bit is set to 1, and all the following bits are set to 0:

SNIPPET
1Binary 10 = Decimal 2
2Binary 100 = Decimal 4
3Binary 1000 = Decimal 8
4Binary 10000000000 = Decimal 1024

When we subtract 1 from any such number, we get a number where ones and zeros are inverted. For example, compare binary representations of decimal 8 and 7:

SNIPPET
1Binary 1000 = Decimal 8
2Binary 0111 = Decimal 7

If we now apply Bitwise AND to these two numbers, the result will be zero. This resulting zero is what ensures we're dealing with a power of two.

(Note that you don't need to enclose number - 1 in parentheses because subtraction has a higher precedence than Bitwise AND.)

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment