Problem statement

Write a function that takes a non-negative integer n and returns the number of 1 bits in its binary representation — its Hamming weight.

Example 1

Input: n = 11
Output: 3
Explanation: 11 is 1011 in binary.

Example 2

Input: n = 128
Output: 1

Example 3

Input: n = 0
Output: 0

Constraints

• 0 <= n <= 2147483647

Follow-up: If this function is called many times, how would you optimise it?

Hints for Number of 1 Bits

1. Hint 1

   Test the lowest bit with n & 1, then shift right, until nothing is left.

2. Hint 2

   n & (n - 1) clears the lowest set bit, so a loop over that runs once per 1 bit instead of once per bit.

3. Hint 3

   Use a logical (unsigned) shift so the loop terminates.

How to solve Number of 1 Bits

n & (n - 1) clears the lowest set bit; loop until zero and count the iterations.

Approach

1. While n != 0: n &= n - 1, increment the count.
2. Return the count.

Why it works

Subtracting one borrows through the trailing zeros and flips the lowest set bit, so the AND removes exactly that bit each iteration.

Complexity

• Time — O(popcount)
• Space — O(1)

Pitfalls

• In a signed 32-bit language use a logical shift if you shift instead, or the loop never ends for negatives.

Reference solution

Python

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

Java

public static int hammingWeight(int n) {
    int count = 0;
    int v = n;
    while (v != 0) {
        v &= v - 1;
        count++;
    }
    return count;
}

C++

int hammingWeight(int n) {
    unsigned int v = (unsigned int) n;
    int count = 0;
    while (v) {
        v &= v - 1;
        count++;
    }
    return count;
}

JavaScript

var hammingWeight = function(n) {
    let count = 0;
    let v = n >>> 0;
    while (v > 0) {
        v &= v - 1;
        count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More bit manipulation problems

• Convert Sorted Array to Binary Search Tree Easy
• Longest Nice Substring Easy
• Majority Element Easy
• Merge k Sorted Lists Hard
• Sort List Medium
• Convert Sorted List to Binary Search Tree Medium