LeetEye LeetEye
Easy Bit Manipulation ~5 min

Number of 1 Bits

bit-manipulation number-of-1-bits

Problem

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

Examples

Example 1
Input: n = 00000000000000000000000000001011
Output: 3
Binary has three '1' bits.
Example 2
Input: n = 00000000000000000000000010000000
Output: 1
Example 3
Input: n = 11111111111111111111111111111101
Output: 31
Key Insight

n & (n-1) clears the rightmost set bit. Count iterations until n becomes 0.

n & (n-1) clears rightmost 1-bit. Count iterations until n = 0. Each iteration = one 1-bit.

How to Approach This Problem

Pattern Recognition: When you see keywords like number of 1 bits bit-manipulation, think Bit Manipulation.

Step-by-Step Reasoning

1 n & (n-1) does:
Answer: Clears rightmost 1 bit
n-1 flips all bits from rightmost 1 to right. AND with n clears that 1.
2 If n = 12 (1100), n & (n-1) = ?
Answer: 8 (1000)
12 = 1100, 11 = 1011. 1100 & 1011 = 1000 = 8.
3 To count 1s, we:
Answer: Count iterations until n = 0
Each n = n & (n-1) removes one 1-bit. Count how many removals.
4 We can also:
Answer: Both A and B
Either works. n & 1 checks last bit, shift right to check next.
5 Brian Kernighan's method iterates:
Answer: Number of 1-bits times
Each iteration removes one 1-bit. Runs exactly count(1s) times.

Solution

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= n - 1  # Clear rightmost 1-bit
        count += 1
    return count

Complexity Analysis

Time O(k)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Bit Manipulation problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye