Problem Description

Given a positive integer n, you need to count how many 1s (set bits) appear in its binary representation.

For example:

• If n = 11, its binary representation is 1011, which contains three 1s, so the answer is 3
• If n = 128, its binary representation is 10000000, which contains one 1, so the answer is 1
• If n = 7, its binary representation is 111, which contains three 1s, so the answer is 3

The solution uses a bit manipulation technique where n & (n - 1) removes the rightmost set bit from n. By repeatedly applying this operation until n becomes 0, we can count the total number of set bits. Each iteration removes exactly one set bit and increments the counter, giving us the final count of 1s in the binary representation.

Intuition

When counting 1s in a binary number, the straightforward approach would be to check each bit position one by one. However, there's a clever observation we can make about binary numbers that leads to a more efficient solution.

Consider what happens when we subtract 1 from a binary number. When we compute n - 1, all the bits after the rightmost 1 (including that 1 itself) get flipped. For example:

• 12 in binary is 1100
• 12 - 1 = 11 in binary is 1011
• Notice how the rightmost 1 at position 2 became 0, and all bits to its right (which were 0s) became 1s

Now, what happens when we perform n & (n - 1)? The AND operation between n and n - 1 effectively removes that rightmost 1 bit:

• 1100 & 1011 = 1000
• The rightmost 1 has been eliminated!

This gives us a powerful technique: each time we perform n = n & (n - 1), we remove exactly one set bit from n. If we keep doing this operation until n becomes 0, the number of iterations we performed equals the number of 1s that were originally in the number.

The beauty of this approach is that we only iterate as many times as there are 1s in the number, rather than checking all 32 bit positions. For a number with only a few set bits, this is much more efficient.

Solution Approach

The implementation uses Brian Kernighan's algorithm to count set bits efficiently. Here's how the solution works step by step:

1. Initialize a counter: We start with ans = 0 to keep track of the number of set bits found.

2. Main loop: We continue looping while n is not zero. When n becomes 0, it means all set bits have been processed.

3. Clear the rightmost set bit: In each iteration, we perform n &= n - 1. This operation clears the rightmost set bit in n. Let's trace through an example:

   • If n = 12 (binary: 1100)
   • n - 1 = 11 (binary: 1011)
   • n & (n - 1) = 1100 & 1011 = 1000 (cleared the rightmost 1)

4. Increment counter: After clearing each set bit, we increment ans by 1 to count that we've found and removed one set bit.

5. Return the result: Once the loop exits (when n becomes 0), ans contains the total count of set bits.

Example walkthrough with n = 11 (binary: 1011):

• Iteration 1: n = 1011 & 1010 = 1010, ans = 1
• Iteration 2: n = 1010 & 1001 = 1000, ans = 2
• Iteration 3: n = 1000 & 0111 = 0000, ans = 3
• Loop exits, return 3

The time complexity is O(k) where k is the number of set bits, which is at most O(log n). The space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with n = 13 (binary: 1101).

Initial state: n = 13 (binary: 1101), ans = 0

Iteration 1:

• Current n = 1101
• Calculate n - 1 = 12 (binary: 1100)
• Notice: subtracting 1 flipped the rightmost 1 (at position 0) to 0, and all bits to its right (none in this case)
• Perform n & (n - 1) = 1101 & 1100 = 1100
• The rightmost 1 has been removed!
• Update: n = 1100, ans = 1

Iteration 2:

• Current n = 1100
• Calculate n - 1 = 11 (binary: 1011)
• Notice: the rightmost 1 (at position 2) became 0, and bits to its right (positions 0-1) flipped from 00 to 11
• Perform n & (n - 1) = 1100 & 1011 = 1000
• Another set bit removed!
• Update: n = 1000, ans = 2

Iteration 3:

• Current n = 1000
• Calculate n - 1 = 7 (binary: 0111)
• Notice: the rightmost (and only) 1 at position 3 became 0, all bits to its right became 1s
• Perform n & (n - 1) = 1000 & 0111 = 0000
• Last set bit removed!
• Update: n = 0, ans = 3

Loop exits because n = 0

Result: Return ans = 3

The original number 13 (binary: 1101) had exactly 3 set bits, which matches our count. Each iteration removed exactly one set bit until none remained.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k), where k is the number of 1-bits in the binary representation of n.

The key insight is that the operation n &= n - 1 removes the rightmost 1-bit from n in each iteration. This operation is known as Brian Kernighan's algorithm. The loop continues until all 1-bits are removed (when n becomes 0), so it executes exactly k times, where k is the Hamming weight (number of 1-bits).

In the worst case, when all bits are 1, k could be O(log n) since an integer n has at most log₂(n) + 1 bits. However, the algorithm only iterates for the actual number of 1-bits present, making it more efficient than checking every bit position.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space: the counter variable ans. No additional data structures or recursive calls are made, so the space complexity is constant regardless of the input size.

Common Pitfalls

1. Attempting to use string conversion for bit counting

Many developers initially try to convert the number to a binary string and count '1' characters:

# Inefficient approach
def hammingWeight(self, n: int) -> int:
    return bin(n).count('1')

While this works, it's less efficient due to string conversion overhead and doesn't demonstrate understanding of bit manipulation.

2. Using right shift with modulo checking

Another common but less optimal approach:

# Less efficient - checks every bit position
def hammingWeight(self, n: int) -> int:
    count = 0
    while n:
        count += n & 1  # Check if last bit is 1
        n >>= 1         # Right shift by 1
    return count

This checks all bit positions even if many are zeros, making it O(log n) instead of O(k) where k is the number of set bits.

3. Incorrect operator precedence with n-1

A subtle mistake when not using parentheses properly:

# WRONG - operator precedence issue
n = n & n - 1  # This is interpreted as (n & n) - 1

Solution: Always use parentheses to ensure correct operation:

# CORRECT
n = n & (n - 1)  # or use compound assignment: n &= n - 1

4. Not handling edge cases properly

Forgetting that the algorithm naturally handles n=0:

# Unnecessary edge case check
def hammingWeight(self, n: int) -> int:
    if n == 0:  # This check is redundant
        return 0
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

The while loop condition already handles n=0 correctly, making the explicit check unnecessary.

5. Misunderstanding how n & (n-1) works

Some developers mistakenly think this operation counts bits or does something else:

# WRONG - trying to use the operation result as count
def hammingWeight(self, n: int) -> int:
    count = 0
    while n:
        count = n & (n - 1)  # WRONG - this doesn't give you the count
        n = n & (n - 1)
    return count

Solution: Remember that n & (n-1) only clears the rightmost set bit. You must maintain a separate counter to track how many times this operation is performed.