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.)
xxxxxxxxxx
const isPowerOfTwo = number => {
return (number & number - 1) == 0;
}
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment