In this article, we are going to learn the most efficient and popular solutions to a very common problem – checking if a number is a power of 2. While it seems an easy task, we will see that some of these solutions are faulty in presence of corner cases.
In the following sections, we are only going to describe constant-time solutions. Let’s dive in!
A Solution Based on the Logarithm
The Math library provides the Log2() method, which accepts a double and returns its logarithm base 2. We know that the logarithm is the inverse of exponentiation, so how can we use this to establish if the given number is a power of 2? We need to make sure that Log2() returns a round number:
var log = Math.Log2(n); return log == Math.Floor(log) && n > 0;
The ending n > 0 is necessary because this expression evaluates to true:
Math.Log2(0) == double.NegativeInfinity && Math.Floor(double.NegativeInfinity) == double.NegativeInfinity
We have one last unsolvable problem: we are working with doubles, which are affected by the rounding error. This means that, for huge numbers, the result could be wrong. For example, with n = 9223372036854775809, that function returns true, although it is not a power of 2 (the last digit is odd).
Let’s now see some reliable and correct approaches!
Check Power of 2 With a Tricky Bitmask Solution
This and the next solutions are based on a simple and convenient property of all the powers of 2: at the bit-level, a power of 2 has only one bit set to 1, all the others are 0. Let’s see a first solution based on this idea:
(n & (-n)) == n && n > 0;
At the bit-level, -n means applying the two’s complement operation to n. For example, let’s take n = 16:
16 0b0001_0000 & -16 0b1111_0000 = ------------------- 16 0b0001_0000
This equivalence is true only when n has a single bit set to 1. Let’s prove it by considering once again the binary representation of 16: 0b0001_0000. If we negate this sequence of bits, we get 0b1110_1111, then we have to add 1 to obtain the two’s complement value of 16, which is 0b1111_0000.
When adding 1 to 0b1110_1111, the carry is propagated 4 times, setting again to 1 the only bit that was initially up in 16. The carry’s propagation is what makes the bit-wise & return a non-zero result, but this is not enough because the expression’s result must be n.
Another Example
Let’s see what happens with n = 20, where 2 bits are set in its binary representation:
20 0b0001_0100 & -20 0b1110_1100 = ------------------- 4 0b0000_0100
Here, the carry is propagated only twice, eventually setting the 3rd bit to 1 (starting from the least significant bit). What about the 5th bit? That bit is &ed with the negation of itself, so the final result will not have that bit set. This simple demonstration should have convinced you that only the rightmost 1-bit is preserved when performing n & (-n). Therefore, the only way to make that expression return n is to choose a number having a single bit set to 1, i.e. a power of 2.
Again, n = 0 is a problematic case: (0 & 0) == 0. The fix is the same, let’s just make sure that n starts from 1.
Unfortunately, it’s not over yet. What if the type of n is not int but ulong? In this case, the compiler complains because we’re working with an unsigned type. As a work-around, we can rewrite -n as ~n + 1, which is the two’s complement of n. The final solution becomes:
(n & (~n + 1)) == n && n > 0
Let’s now see another approach based on the bitmask concept.
A Better Bitmask Solution
The probably most popular solution is:
(n & (n - 1)) == 0 && n > 0
The underlying logic is not so different from the one of the previous solution. In this case, instead of negating the number, we subtract 1 from it. This means that if the number has only one bit set to 1, i.e. is a power of 2, n - 1 resets that bit and set all the following 0s to 1s. In such cases, n & (n - 1) is always 0:
16 0b0001_0000 & 15 0b0000_1111 = ------------------- 0 0b0000_0000
Instead, if we set an additional bit to 1, like with n = 20:
20 0b0001_0100 & 19 0b0001_0011 = ------------------- 16 0b0001_0000
The subtraction would just affect the least significant bit, leaving the other one unaltered.
We should not be surprised to see n > 0, for n = 0 the expression would mistakenly return true.
We’ve seen several approaches, but what about the in-built options?
The Built-in Solution
Starting from .NET 6, there is a built-in method called BitOperations.IsPow2() that does exactly what we have been trying to do until now. We’ve implemented this method as the second bitmask-based solution, but with a further optimization:
[MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool IsPow2(int value) => (value & (value - 1)) == 0 && value > 0;
As the name suggests, the attribute MethodImplOptions.AggressiveInlining tells the JIT compiler to override the heuristics and inline the method when possible.
Conclusions
When we use .NET 6, IsPow2() is the way to go: it is an optimized version of the faster algorithm we have seen. For all the previous versions of .NET 6, we are forced to create our utility method, that wraps the current implementation of IsPow2().
