In this blog post we will learn about two algorithms that allow us to quickly check that a given integer is a power of two. Both of these algorithms use only bit operators - they are very efficient.

#### Algorithm I

We will start by looking at the algorithm implementation, then I will explain how it works:

Before we move on it is a good time to remind ourselves that
along an algorithm implementation we
should always specify the range of valid inputs
and expected outputs.
In the code above I used Javadoc comments to state that our algorithm
accepts any number (positive, negative or zero) but it
considers only positive numbers to be powers of two.
For example `isPowerOfTwo(8)`

should return `true`

but
`isPowerOfTwo(-16)`

should return `false`

.

Now let’s explain how the algorithm works. If we look at the binary representation of the powers of two we can see the following bit pattern - there is only a single bit set:

Now comes the tricky part. Computers use two’s complement encoding to efficiently store and perform operations on both positive and negative numbers.

To explain how two’s complement works we must first
realise that pure binary encoding can only be used
to store positive numbers:
One naive extension to pure binary encoding that supports
storing negative numbers is to
sacrifice MSB (the most significant bit) to represent number sign:
But this solution comes with its own problems,
for example we will end up with two different
bit patterns that represent the value of zero (`+0`

and `-0`

).
This also unnecessary complicates CPU design
(we will need two different circuits to perform unsigned and signed
arithmetic) and reduces the range of
possible values that can be represented within a single byte
(again because zero is now unnecessarily
represented by two distinct values).

Two’s complement encoding solves all these problem. The main idea is to assign negative weight to the most significant bit of the number, for example: The positive numbers have the same representation as they have in pure binary encoding. There is also a simple procedure to negate a number, first negate all bits and then add one to the result:

Above procedure works for all numbers except one - the maximum negative
value (`-128`

for a single byte, `-2147483648`

for a 4-byte `int`

):
This is the consequence of the fact that
range of numbers that can be represented using two’s complement
is asymmetric around zero. For example in a single byte we can
represent values from `-128`

up to `127`

.

Since we are here it is also worth to mention that we may use
the same addition algorithm to add numbers encoded in pure
binary encoding and in two’s complement encoding.
Subtraction is also very easy. Say you want to subtract
numbers `a`

and `b`

, you just negate `b`

(using `NOT`

and `INC`

instructions)
and then add it to `a`

.

Now let’s go back to our algorithm.
Let’s assume that we have a number that is a power of two,
such a number has only one bit set. So we may assume that
our number `n`

has form:

As discussed above arithmetic negation is performed by first negating all bits and then adding one, in our case:

As we can see `n`

and `-n`

share a single common bit, `AND`

ing both
values yields:

So we ended up with the same value as we started.
In other words `(n & -n) == n`

returns true.
This is illustrated for `n = 32`

on the diagram below:

Now consider a number that is not a power of two, such a number will have at least two bits set (we will deal with zero later). We will divide number into three parts, the bits before first set bit on the left, the bits after the last set bit on the right and the middle bits. Let’s see what will happen when we use our algorithm on such a number:

I used `?`

to mark middle bits that can have any value.
The most important observation is that the leftmost set bit
in `n`

is cleared after negation.

Now let’s see what will be returned by `AND`

:

As we can see all bits before `?`

are cleared after performing `AND`

operation. This guarantees that `(n & -n)`

expression returns
different value than `n`

which has one bit set before `?...?`

bits.
And so `(n & -n) == n`

returns `false`

as expected.

Diagram below illustrates how algorithm works for `n = 36`

:

There are two special values that need more attention.
One is of course zero which is handled explicitly by the condition
`(number > 0)`

. The other value is `Integer.MIN_VALUE`

.
The `Integer.MIN_VALUE`

may be treated either as a power of two
(it has only single bit in the binary representation) or not.
This depends on how we want to tread `int`

value in Java
(as a singed number or as an unsigned one).
At the beginning we decided that our algorithm accepts negative values
and so `number`

is a signed value.
To be consistent we again use `(number > 0)`

condition to return
`false`

for `Integer.MIN_VALUE`

.

#### Algorithm II

Again we will start with the implementation:

This algorithm is much more simpler than previous one. So how does it work? We already know that numbers that are powers of two have only single bit set in their binary representation:

When we substract one from such a number we get:

As we can see the leftmost bit of `n`

is cleared
after subtraction. When we `AND`

`n`

and `n-1`

we get zero:

Numbers that are not powers of two (except zero) have at least two bits set. Again we use our trick with dividing number into three parts: bits before first set bit, bits after last set bit and the middle bits.

This shows us that the leftmost bit of `n`

is not cleared by the `AND`

operation and so the final value cannot be equal to zero.

Two special cases for zero and maximum negative value are
handled in exactly the same way as in Algorithm I by `(number > 0)`

condition.

Diagram below illustrates how Algorithm II works for `113`

:

#### Versions of algorithm I and II for unsigned numbers

Some programming languages e.g. C# and C++ supports
unsigned numbers. Such numbers can only store zero and positive values.
We may use the fact that all values are non-negative to
simplify condition `(number > 0)`

into `(number != 0)`

which
may be better optimized by some compilers.

It may be surprising that unsigned numbers support
arithmetic negation operator `(-)`

.
For them negation just means combination of `NOT`

and `INC (+1)`

instructions that we described previously.

Here are versions of both algorithms that operate on unsigned numbers in C#:

#### JavsScript peculiarities

JavaScript uses `double`

type to represent all numbers.
`double`

s are capable of accurately storing integers in range
`-2^53 .. +2^53`

. Unfortunately when we perform bit operations
in JavaScript
both operands are first converted to 32 bit signed integers and
then operation proceeds.
This means that both presented algorithms will work in JS only
for numbers in range `-2^30 .. +2^30-1`

.
This is demonstrated by program: