Bitwise nuggets: check if a number is a power of 2
Post
Cancel

# Bitwise nuggets: check if a number is a power of 2

Here we discuss how to determine whether a given number is a power of 2.

As we know, a number is a power of 2 if it has only one of its bits set to 1. Such numbers have a very interesting property that we use all the time for creating bit masks: if we subtract 1 from a power of 2, we get a sequence of `1`s starting from the next most significant bit with respect to the bit that is set in out input number.

If we apply the logical `AND` operator to the input number and this sequence of `1`s, we get 0. For a number that is not a power of 2, applying the `AND` operator to the number and the number from which we subtract 1 will always result in a value different from zero.

Let us see a couple of examples to better visualize what this means.

Here, we can see that 64 is a power of 2 since the bitwise `AND` with 63 yields all zeros:

When a number is not a power of 2, the bitwise `AND` between that number and the number from which we subtract 1 will always yield something other than zero:

Here is how this algorithm can be implemented in C:

```1 2 3 4 5 6 7 #include <stdbool.h> // Determines whether the specified number is a power of two. bool is_power_of_two(int number) { if (number == 0) return false; return (number & (number - 1)) == 0; } ```

Want to see more bitwise logic? There’s a whole repository on my GitHub on bit fiddling.