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:
/**
* Checks if a {@code number} is a power of two.
* <p>
* Zero and negative numbers are not considered powers of two.
* </p>
* @param number any integer.
* @return {@code true} when {@code number} is a power of two,
* {@code} false otherwise.
*/
boolean isPowerOfTwo(int number) {
return
( (number & (-number)) == number ) &&
(number > 0);
}
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:
0...010...0
As discussed above arithmetic negation is performed by first negating all bits and then adding one, in our case:
0...010...0
1...101...1 (NOT)
1...110...0 (+1)
As we can see n
and -n
share a single common bit, AND
ing both
values yields:
0...010...0 n
1...110...0 -n
AND
0...010...0 = n
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:
0..01?...?10..0 n
1..10?...?01..1 (NOT)
1..10?...?10..0 (+1) = -n
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
:
0..01?...?10..0 n
1..10?...?10..0 -n
AND
0..00?...?10..0 != n
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:
/**
* Checks if a {@code number} is a power of two.
* <p>
* Zero and negative numbers are not considered powers of two.
* </p>
* @param number any integer.
* @return {@code true} when {@code number} is a power of two,
* {@code} false otherwise.
*/
boolean isPowerOfTwo2(int number) {
return
( (number & (number-1)) == 0 ) &&
(number > 0);
}
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:
0..010..0
When we substract one from such a number we get:
0..010..0 n
0..001..1 n-1
As we can see the leftmost bit of n
is cleared
after subtraction. When we AND
n
and n-1
we get zero:
0..010..0 n
0..001..1 n-1
0..000..0 (n AND n-1)
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.
0..01?...?10..0 n
0..01?...?01..1 n-1
0..01?...?00000 (n AND n-1)
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#:
/// <summary>
/// Checks if a <paramref="number" /> is a power of two.
/// </summary>
/// <remarks>
/// Zero is not considered power of two.
/// </remarks>
/// <param name="number">Any unsigned value</param>
/// <returns>
/// <c>true</c> when <c>number</c> is a power of two,
/// <c>false</c> otherwise.
/// </returns>
bool IsPowerOfTwo(uint number) {
return
( (number & (-number)) == number ) &&
(number != 0);
}
/// ... documentation ommited ...
bool IsPowerOfTwo2(uint number) {
return
( (number & (number-1)) == 0 ) &&
(number != 0);
}
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:
function isPowerOfTwo(number) {
return(
(number & (-number)) == number &&
(number > 0));
}
let two_power_30 = Math.pow(2, 30);
// true
console.log(isPowerOfTwo(two_power_30));
let two_power_31 = Math.pow(2, 31);
// false
console.log(isPowerOfTwo(two_power_31));