191 - Number of 1 Bits

Difficulty: Easy | Pattern: Bit Manipulation | Company tags: Apple, Microsoft, Adobe

Problem Statement

Write a function that takes the binary representation of a positive integer and returns the number of set bits (also known as the Hamming weight).

Example 1:

Input: n = 11 (binary: 1011)
Output: 3

Example 2:

Input: n = 128 (binary: 10000000)
Output: 1

Example 3:

Input: n = 2147483645 (binary: 1111111111111111111111111111101)
Output: 30

Approach 1: Brian Kernighan's Algorithm — O(k)

Key insight: n & (n-1) clears the lowest set bit. Count how many times we can do this.

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1  # remove lowest set bit
        count += 1
    return count

This runs in O(k) where k = number of set bits — faster than O(32) when few bits are set.

Why n & (n-1) works: n-1 flips the lowest set bit and all trailing zeros. ANDing with n keeps everything above the lowest set bit, but clears it.

Example: n = 1100, n-1 = 1011, n & (n-1) = 1000 (lowest set bit cleared).

Approach 2: Shift and Count — O(32)

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        count += n & 1  # check last bit
        n >>= 1         # shift right
    return count

Approach 3: Python Built-in

def hammingWeight(n: int) -> int:
    return bin(n).count('1')

Dry Run (Kernighan)

n = 11 (binary: 1011)

Step	n (binary)	n & (n-1)	count
1	1011	1010	1
2	1010	1000	2
3	1000	0000	3

count = 3 ✓

Edge Cases

• n = 0 → 0 set bits
• n = all 1s (e.g., 2³²-1) → 32 set bits
• Powers of 2 → exactly 1 set bit

Complexity

Approach	Time	Space
Brian Kernighan	O(k) where k = set bits	O(1)
Shift and count	O(32) = O(1)	O(1)
bin().count()	O(32) = O(1)	O(log n) for string

Related: LeetCode 338 (Counting Bits) uses the same n & (n-1) insight for DP across a range.