Leetcode – Number of 1 Bits Solution in Python

Spread the love

In computer science, understanding binary representation and bitwise operations is fundamental. The Number of 1 Bits problem on LeetCode is an excellent starting point for anyone looking to gain or enhance their knowledge in bit manipulation. In this extensive article, we will explore the Number of 1 Bits problem, examine various techniques to solve it, and implement these solutions in Python.

Problem Statement

The Number of 1 Bits problem is listed as problem number 191 on LeetCode. Here’s the problem statement:

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1:
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three ‘1’ bits.

Example 2:
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one ‘1’ bit.

Understanding the Problem

The task is simple: we are given an unsigned 32-bit integer, and we need to determine how many bits are set to 1 in its binary representation.

Approach 1: Iteration and Bit Masking

One of the most straightforward approaches is to iterate through each of the 32 bits of the number and count how many of them are set to 1. We can use a mask that isolates one bit at a time and checks if it is 1.

def hammingWeight(n):
    count = 0
    # Using a mask to isolate each bit
    mask = 1
    for i in range(32):
        # If the ith bit is set
        if n & mask:
            count += 1
        # Shift the mask to the left
        mask <<= 1
    return count

This approach has a time complexity of O(1) since we always iterate 32 times, and space complexity is O(1).

Approach 2: Bit Manipulation Trick

An optimization to the first approach involves using a neat bit manipulation trick. Instead of checking each bit, we can directly jump to the bits that are set to 1. The trick is to use the fact that for a binary number n, the bitwise operation n & (n - 1) flips the least-significant 1-bit in n to 0.

def hammingWeight(n):
    count = 0
    # Flip the least-significant 1-bit to 0 until n becomes 0
    while n:
        count += 1
        n &= n - 1
    return count

This approach has a time complexity of O(k), where k is the number of bits set to 1, and space complexity is O(1).

Approach 3: Using Built-in Functions

Python provides built-in functions that can be used to solve this problem with much shorter code. The bin function returns a string representation of the binary representation of a number, and we can simply count the number of ‘1’ characters in this string.

def hammingWeight(n):
    # Convert to binary and count the number of '1's
    return bin(n).count('1')

This approach has a time complexity of O(1) and space complexity of O(1).

Conclusion

The Number of 1 Bits problem is not only a great exercise in understanding binary representation and bitwise operations but also has real-world applications. Through the various approaches we have explored, we can appreciate the power and elegance that bit manipulation can bring to solving problems efficiently.

Leave a Reply