The moment you learn about computers, you learn about binary numbers.

It is how the computer brain works. The little thinking bits are either on or off, 1 or 0, binary. It's so common it is noted directly in the Python core documentation. In fact, we can show it using addition:

.1 + .2
>>> 0.30000000000000004

Our decimal number .1 and .2 cannot be represented entirely without trouble using binary numbers. In fact, they both do not have a finite representation in binary. The computer must then try and approximate a number with a series of fractions.

The computer cuts off this number at certain point of precision, and as unlucky as we are, this results in our computer return `0.30000000000000004`` as the resulting sum of 0.1 and 0.2. What is easy for us in decimal numbers is hard in binary. Especially, people with a more classical education in computer science learn this very early and have probably stopped reading a long time ago, but now it gets curious.

A computer that is good with binary numbers should be good with powers of two.

2**56
>>> 72057594037927936

So in my youthful naivité I assumed that the base 2 logarithm of a binary number would be a good test if an arbitrary number is a power of 2. Why, you might say? One-hot encoding provides a number equal to exactly one one and the rest is only zeros. So, exactly a power of two.

int("001", 2)
>>> 1
int("010", 2)
>>> 2
int("100", 2)
>>> 4

That means we can use logarithms and check if the number is an integer. Python has all the tools for it! We can import math and use the method available for floating point numbers named .is_integer()

import math

math.log(2**55, 2)
>>> 55
math.log(2**55, 2).is_integer()
>>> True

But there's a problem. Understanding binary numbers and logarithms as humans does not necessarily mean it translates to computers that, in theory, should be good with powers of 2. Mathematically, the algorithm uses a change of base, so \(\\log_2(16) = \\ln(16) / \\ln(2)\), with \(\\ln\) being the natural logarithm to the base of Euler's number e. The program has to numerically search for the result and this breaks down, here:

math.log(2**9999999999, 2)
>>> 999999999.0000001

So we have a choice and can use

math.log2(2**9999999999)
>>> 999999999.0

which has higher precision, but might eventually fail with unpredictable failure modes. The algorithm should be exact, because it uses floating point decomposition, such that x = m * 2.**e though, so you could take your chances. Alternatively, we can use an exact solution that does not rely on math. While the mathematical solution "should" be exact, it is not for a computer. However, treating the binary number as bits, leads us to the solution. The correct way to check if a number is a power of two in Python, using the bit-wise and (&) operator, we can use a nifty trick, considering n is our number:

(n & (n - 1) == 0) and n != 0

Let's see how that works. Let's say we are working with \(n = 8\), which is simply

int("1000", 2)
>>> 8

Then n-1 is 7, which is

int("0111", 2)
>>> 7

The -1 therefore acts as a flip for every bit of our number. A zero becomes one and a one becomes zero. The genius part is that the & operator is the bit-wise comparison, so each digit in each number is compared directly. 0 & 1 is 0, and gives us a total of 0 only and only when the number is a power of 2 with a single digit being 1. To quickly confirm and wrap this up, let's have a look at \(n = 3\), this is 011 and \(n - 1 = 2\) is 010. Then 011 & 010 results in 010 instead of a total of zero.

What a neat way to solve a problem exactly and without imports. This is how I learned that logarithms on computers are much more complicated than I anticipated. In the end, they're better avoided despite feeling smart when we understand them and find a possible solution involving them on binary numbers (and honestly decimals too).