Problem 34.2 · Bit ManipulationEasy

Number of 1 Bits

What it teaches: Brian Kernighan's loop: n & (n − 1) removes one set bit per step.

Practise it on judges as “Number of 1 Bits”.

The problem

Return the number of set bits in the binary representation of a positive integer n.

Example 1

Input: n = 11
Output: 3

1011.

Constraints

1 ≤ n ≤ 2³¹ − 1

Pattern clues in the wording

→ Count ones

These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int hammingWeight(int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 11	3
2	n = 128	1
3	n = 2147483645	30

From slow to fast

Approaches

1. Drop the lowest bit · O(number of ones)

Drop the lowest bit

Time O(number of ones) Space O(1)

while n ≠ 0: n &= n − 1; count++.

Approach 1

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

Verdict: Integer.bitCount does the same in one instruction.

Before you submit

Edge cases and common mistakes

Test these inputs

Powers of two (1)
2³¹ − 1 (31)

Mistakes people make

Using n >> 1 in a loop on negative inputs (never reaches 0; use >>>).

Interview

Follow-up questions

How do you get the Hamming distance between x and y?

Command Palette

The problem

Approaches

Drop the lowest bit

Edge cases and common mistakes

Follow-up questions