How do you approach Number of 1 Bits (Hamming Weight)?

The straightforward loop shifts right 32 times and tests the low bit each iteration.

What is the time complexity of Number of 1 Bits (Hamming Weight)?

Time complexity: O(number of set bits), at most O(32).. Space complexity: O(1).

What are common mistakes on Number of 1 Bits (Hamming Weight)?

Shifting by at least the word width, which is undefined or wraps depending on the language. Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends. Precedence: & and | bind more loosely than the comparison operators, so a & 1 == 0 does not mean what it looks like.

gitGood.dev

← Back to problems

Number of 1 Bits (Hamming Weight)

EasyAlgorithms

Description

Given a non-negative integer, return the number of 1 bits in its binary representation - its Hamming weight.

Example 1

Input: n = 11

Output: 3

Example 2

Input: n = 128

Output: 1

Example 3

Input: n = 0

Output: 0

Constraints

- 0 <= n <= 2^31 - 1 - Aim to do better than checking all 32 bit positions.

Number of 1 Bits (Hamming Weight): approach, complexity and pitfalls

An easy bit manipulation problem, graded against 6 test cases (3 of them hidden).

The pattern: Bit Manipulation

XOR, masks, and shifts - constant-space tricks for counting and pairing.

Reach for it when you see: "Appears once/twice", powers of two, or an explicit O(1) space requirement.

If you are stuck

Show the 3-step hint ladder

The straightforward loop shifts right 32 times and tests the low bit each iteration.
There is a better trick: n & (n - 1) clears the LOWEST set bit and leaves everything else alone.
So loop while n is non-zero, applying that operation and counting - the loop runs once per set bit, not once per bit position.

The optimal approach

Show the approach: n & (n - 1) clears the lowest set bit

The baseline solution shifts right 32 times, testing the low bit each round. Correct, and always exactly 32 iterations regardless of the input.

Brian Kernighan's trick does better. Subtracting 1 flips the lowest set bit to 0 and turns every zero below it into a 1; ANDing with the original therefore clears exactly that lowest set bit and preserves everything above. Repeating until the value is zero runs once per set bit, so a number with three 1s takes three iterations rather than 32.

Worked example: `12` is `1100`. `12 & 11` is `1100 & 1011` = `1000`, and `8 & 7` is `1000 & 0111` = `0`. Two iterations, two set bits.

The same identity is the basis of the classic `n & (n - 1) === 0` test for powers of two - a number with exactly one set bit becomes zero after one clear.

One JavaScript caveat: bitwise operators coerce to signed 32-bit, so values at or above 2^31 need `>>> 0` or a comparison against `0` written carefully. Python's unbounded integers have no such issue.

Time: O(number of set bits), at most O(32).
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Bit Manipulation mistakes

These apply to the pattern as a whole, not just this problem.

Shifting by at least the word width, which is undefined or wraps depending on the language.
Using an arithmetic right shift where a logical one is meant - the sign bit propagates and the loop never ends.
Precedence: `&` and `|` bind more loosely than the comparison operators, so `a & 1 == 0` does not mean what it looks like.