Number of 1 Bits: Brian Kernighan Pattern

Learning Outcome

After this lesson, you should be able to count set bits by clearing one set bit per loop.

Problem Statement

Given an integer n, return the number of 1 bits in its binary representation.

Brute Force Approach

Check every bit position one by one. This is fine for fixed width but does unnecessary work for sparse numbers.

Optimized Approach

Use Brian Kernighan's trick: n & (n

• 1. removes the lowest set bit each time, so the number of loop iterations equals the number of 1 bits.

Exact Pseudocode

count = 0
while n != 0:
  n = n & (n - 1)
  count += 1
return count
  

Reference Code

class Solution:
    def hammingWeight(self, n):
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
  

Sample Dry Run

Complexity

Edge Cases

• n = 0 should return 0.
• Use unsigned types in C++ when the prompt treats n as unsigned.
• A signed right shift approach can be tricky for negative values.

Interview Checklist

• Use n &= n

  • 1 to remove one set bit.
• Increment count once per removal.
• Stop when n becomes zero.

FAQs