While resolving some problems on LeetCode, I came across an interesting challenge: "The Power of Two" The main objective here is to determine whether a given number is a power of two. An integer 'n' is considered a power of two if there exists an integer 'x' such that n == 2^x. I solved the problem and reviewed my previous submission from October 2022, only to find that I had arrived at the same solution once again. Determined to understand the concept of powers of two better, I delved into the question of what defines a power of two. This exploration led me to the realization that converting a decimal to binary reveals a distinctive pattern: a power of two in binary form has and only has one '1'. This insight reminded me of the concept of Hamming weight.

Hamming Weight

Before diving into the solution, let's delve into Hamming weight. Hamming weight is all about counting the number of '1' bits in a binary sequence. While it may seem straightforward, its beauty lies in its simplicity. In the realm of powers of two, a fundamental concept in computer science, Hamming weight shines brightly. Consider any power of two, like 2⁵ (32). Representing this in binary yields '100000.' The Hamming weight of this binary sequence is 1 – a lone '1' standing proudly amidst a sea of '0's. This pattern repeats itself for every power of two.

Hamming weight goes beyond numbers; it finds applications in error detection and correction codes, cryptography, and various algorithms. In essence, it's a simple yet powerful tool crucial for the robustness of digital systems.

Let's Solve

Before delving into Hamming weight solution, let's review my initial solutions in Python, including a loop-based naive approach and a recursive solution.

Naive approach:

solution.py

def isPowerOfTwo(self, n: int) -> bool:
    if n <= 0:
        return False
    
    while n % 2 == 0:
        n //= 2
    return True if n == 1 else False

Naive solution, right? Going through a loop and checking for a remainder, then dividing by two.

Recursion approach:

solution.py

def isPowerOfTwo(self, n: int) -> bool:
    if n == 1:
        return True
    if n % 2 != 0 or n == 0:
        return False
    return self.isPowerOfTwo(n/2)

So, can we make it better? Yup, by now we have a basic idea about hamming weight. It's all about counting '1's in binary. For our problem, if a number has only one '1', then it's a power of two. Here's the easy one:

solution.py

def isPowerOfTwo(self, n: int) -> bool:
    # Check if n is positive
    if n <= 0:
        return False

    # Convert n to binary and count '1' bits
    return bin(n).count('1') == 1

Here we are using the Hamming weight method. The bin(n) function converts the integer n to its binary representation. The count('1') method then counts the number of '1' bits in the binary representation. If the count is exactly 1, the function returns True, indicating that the number is a power of two.

But here we are using a built-in function from Python. Is there any way to avoid it? Or let's imagine we are using some other programming language that doesn't have these built-in functions. I know C++, C#, and Java also have built-in functions for counting bits, but many languages do not, like JavaScript, for example. So let's look for another solution. Anyways, here we are working with bits, right? What about bit manipulation techniques? The name suggests that we have to deal with bits and somehow manipulate them. So here's a new approach:

solution.py

def isPowerOfTwo(self, n: int) -> bool:
    return n and (n & (n - 1)) == 0

Looks may be confusing; let's break it down:

In the expression n & (n-1), if the result is 0, then 'n' is a power of 2. Additional checks account for 0 as a special case. Therefore, our solution becomes n && (n & (n-1)) == 0

Deeper Explanation

Still finding it confusing? Let's dive deeper into what n & (n-1) does:

It's figuring out if 'n' is either 0 or an exact power of two.

The logic works because a binary power of two is of the form 1000...000, and subtracting one will give you 111...111. When you AND those together, you get zero, as demonstrated below:

playground

    1000 0000 0000 0000
  &  111 1111 1111 1111
    ==== ==== ==== ====
  = 0000 0000 0000 0000

Any non-power-of-two input value (other than zero) will not give you zero when you perform that operation.

Let's try it for some number combinations:

playground

    ----- binary ----
    n    n     n-1     n&(n-1)
    --  ----   ----   --------
    2   0010   0001    0000  --> power of two
    3   0011   0010    0010
    4   0100   0011    0000  --> power of two
    7   0111   0110    0110
    8   1000   0111    0000  --> power of two

Still not clear on how 'return n and (n & (n-1)) == 0' is working? Let's take a specific test case and work through it:

Test Case:

Input: 8
Output: true
Explanation: 2^3 = 8

Let's do it:

playground

    Formula: n && (n&(n-1)) == 0

    8 and (8 & (8-1)) == 0
    8 in binary --> 1000 
    8 - 1 = 7 in binary --> 0111
    1000 & 0111 = 0000 --> Bingo! We have 0, which means its a power of two.

    8 and (0 == 0) 
    true & true -> It returns 'true'

Now, what about avoiding checking whether a result is equal to zero or not? We can make it shorter:

solution.py

def isPowerOfTwo(n):
    return n and not (n & (n - 1))

In Python, we know that the integer 0 is always False. When n is 0 (which is a power of two), it returns 0 for us, and it's False. Then we simply say not False, which is True. So, True and True returns True as a result.

Bonus

Before we conclude the blog, I've included a handy calculator for you. Simply enter a number, click calculate, and it will show you the binary representation along with the count of '1' digits (Hamming weight). It's a straightforward and helpful feature for quickly calculating Hamming weights. Give it a try!

Hamming Weight Calculator

Enter a number:

Conclusion

So, you've dived into the Hamming weight world - basically counting the '1' bits in binary. It's like counting chocolate chips in your favorite cookie recipe but in the tech world!

Coding is like cooking; there are many ways to make a dish, and the same goes for solving problems. It's like having a bunch of recipes for chocolate chip cookies - some are quick, some are fancy, and some might even involve rocket science.

But, let's be real - not all cookie recipes are winners, and not all code solutions are efficient. Knowing the fastest way to whip up your cookies (or code) is the real game-changer. That's where algorithms come in - the secret sauce to making your solutions not just correct but also snappy.

So, embrace the coding kitchen, experiment with recipes (solutions), but always keep that algorithmic spice handy. It's like turning a regular script into the Shakespeare of code – a true masterpiece in the digital realm! Happy coding, and may your cookies (code) always be efficient and delicious! 🍪❤️