C#

Check if a Number is a Power of 2 in C#

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.

To download the source code for this article, you can visit our GitHub repository.

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().

Code Maze

Share
Published by
Code Maze

Recent Posts

HttpClient vs RestSharp – Which One to Use in .NET

HttpClient and RestSharp are HTTP Client libraries that we can use to consume APIs. Working…

Updated Date Jul 7, 2022

Testing Repository Pattern Using Entity Framework

Unit Testing is extremely important for creating robust software. It's very simple in principle but…

Updated Date Jul 6, 2022

Shell Sort in C#

Have you ever needed to sort a list of items, but didn't want to use…

Updated Date Jul 5, 2022

How to Resolve Instances With ASP.NET Core DI

In ASP.NET Core dependency injection, we usually register injectable dependencies at the start of our…

Jul 4, 2022

Ranges and Indices in C#

In this article, we are going to learn more about ranges and indices in C#,…

Updated Date Jul 2, 2022

Code Maze Weekly #128

Issue #128 of the Code Maze weekly. Check out what's new this week and enjoy…

Updated Date Jul 1, 2022