LeetCode 191: Number of 1 Bits Solution in Python Explained

Problem Statement

In LeetCode 191, you’re given a 32-bit unsigned integer n. Your task is to return the number of 1 bits in its binary representation. For example, for n = 11 (binary 00000000000000000000000000001011), there are 3 ones. This differs from bit reversal like LeetCode 190: Reverse Bits, focusing on counting rather than rearranging bits.

Constraints

• Input is a 32-bit unsigned integer (0 to 2³² - 1).
• Output is an integer (number of 1 bits).

Example

Let’s see some cases:

Copy codeInput: n = 11 (binary: 00000000000000000000000000001011)
Output: 3
Explanation: 1s at positions 0, 1, 3 (from right).

Copy codeInput: n = 128 (binary: 00000000000000000000000010000000)
Output: 1
Explanation: 1 at position 7.

Copy codeInput: n = 4294967295 (binary: 11111111111111111111111111111111)
Output: 32
Explanation: All 32 bits are 1.

These examples show we’re counting 1 bits.

Understanding the Problem

How do you solve LeetCode 191: Number of 1 Bits in Python? Take n = 11 (binary: 00000000000000000000000000001011). We need to count the 1s, which are at positions 0, 1, and 3 from the right, totaling 3. A naive approach might convert to a string and count characters, but bit manipulation is more efficient for a fixed 32-bit integer, aiming for O(1) time (constant iterations). This isn’t an array rotation task like LeetCode 189: Rotate Array; it’s about bit-level counting. We’ll use: 1. Bitwise AND with Shift: O(1) time, O(1) space—our best solution. 2. Brian Kernighan’s Algorithm: O(1) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Bitwise AND with Shift Approach

Explanation

Bitwise AND with Shift counts 1 bits by:

• Using a loop over 32 iterations (fixed for 32-bit integer).
• For each iteration:
• Check the least significant bit with n & 1.
• Add to count if 1.
• Shift n right by 1 (n >>= 1) to check the next bit.
• After 32 steps, count holds the total number of 1s.

This achieves O(1) time (constant 32 iterations), O(1) space (few variables), and simplicity by systematically checking each bit.

For n = 11:

• Binary: 00001011.
• Iterate: Check bits 1,1,0,1 (right to left), count = 3.

Step-by-Step Example

Example 1: n = 11 (00000000000000000000000000001011)

Goal: Return 3.

• Step 1: Initialize.
• n = 00000000000000000000000000001011, count = 0.
• Step 2: Iterate 32 times (key steps shown).
• i=0: n & 1 = 1, count = 1, n >>= 1 → 00000101.
• i=1: n & 1 = 1, count = 2, n >>= 1 → 00000010.
• i=2: n & 1 = 0, count = 2, n >>= 1 → 00000001.
• i=3: n & 1 = 1, count = 3, n >>= 1 → 00000000.
• i=4 to 31: n & 1 = 0, count = 3, n = 0.
• Step 3: Finish.
• count = 3.
• Finish: Return 3.

Example 2: n = 128 (00000000000000000000000010000000)

Goal: Return 1.

• Step 1: n = 00000000000000000000000010000000, count = 0.
• Step 2: Key steps:
• i=0 to 6: n & 1 = 0, count = 0.
• i=7: n & 1 = 1, count = 1, n >>= 1 → 00000000.
• i=8 to 31: n & 1 = 0, count = 1.
• Finish: Return 1.

How the Code Works (Bitwise AND with Shift) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef hammingWeight(n: int) -> int:
    # Line 1: Initialize count
    count = 0
    # Start with 0 (e.g., no 1s counted yet)

    # Line 2: Iterate 32 times
    for i in range(32):
        # Fixed 32-bit loop (e.g., 0 to 31)

        # Line 3: Check least significant bit
        if n & 1:
            # Bitwise AND with 1 (e.g., 1011 & 1 = 1)
            count += 1
            # Increment count (e.g., 0 → 1)

        # Line 4: Shift n right
        n >>= 1
        # Move to next bit (e.g., 1011 → 101)

    # Line 5: Return total 1s
    return count
    # e.g., 3 for n=11

This detailed breakdown clarifies how bitwise AND with shift efficiently counts 1 bits.

Alternative: Brian Kernighan’s Algorithm Approach

Explanation

Brian Kernighan’s Algorithm counts 1 bits by:

• Using a loop that runs only for the number of 1s.
• For each iteration:
• Clear the rightmost 1 bit with n & (n-1).
• Increment count.
• Loop ends when n = 0.

It’s a practical alternative, O(1) time (max 32 iterations, fewer if sparse), O(1) space, and clever by reducing n faster than shifting.

For n = 11:

• 11 & 10 = 10, count=1.
• 10 & 9 = 8, count=2.
• 8 & 7 = 0, count=3.

Step-by-Step Example (Alternative)

For n = 11 (00001011):

• Step 1: count = 0, n = 00001011.
• Step 2: Iterate until n = 0.
• n = 11, n-1 = 10, n & (n-1) = 10 (00001010), count = 1.
• n = 10, n-1 = 9, n & (n-1) = 8 (00001000), count = 2.
• n = 8, n-1 = 7, n & (n-1) = 0 (00000000), count = 3.
• Finish: Return 3.

How the Code Works (Brian Kernighan)

Copy codedef hammingWeightBrian(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)  # Clear rightmost 1
        count += 1
    return count

Complexity

• Bitwise AND with Shift:
• Time: O(1) – fixed 32 iterations.
• Space: O(1) – constant space.
• Brian Kernighan’s Algorithm:
• Time: O(1) – iterations = number of 1s (≤ 32).
• Space: O(1) – constant space.

Efficiency Notes

Bitwise AND with Shift is the best solution with O(1) time (predictable 32 iterations) and O(1) space, offering simplicity and clarity—Brian Kernighan’s Algorithm also runs in O(1) time but is faster for sparse numbers (fewer 1s), though slightly less intuitive, making it a clever alternative with equal space efficiency.

Key Insights

• Shift: Checks all bits.
• Kernighan: Clears 1s.
• 32-Bit: Fixed length.

Additional Example

For n = 5 (00000101):

• Goal: 2.
• Shift: Bits 1,0,1 → 2.

Edge Cases

• All Zeros: 0 → 0.
• All Ones: 4294967295 → 32.
• Single 1: 1 → 1.

Both solutions handle these well.

Final Thoughts

LeetCode 191: Number of 1 Bits in Python is a fun bit-counting challenge. The Bitwise AND with Shift solution excels with its straightforward efficiency, while Brian Kernighan’s Algorithm offers a clever twist. Want more? Try LeetCode 190: Reverse Bits for bit reversal or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 191 on LeetCode with 11, aiming for 3—test your skills now!