Skip to main content

26. Number of 1 Bits

easyAsked at Reddit

Count the set bits in a 32-bit integer. Reddit uses this Hamming-weight question to test bitwise tricks — the same primitive used in their feature-flag rollout system where flag-sets are stored as bitmasks.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit phone screen, common bitwise warm-up.

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).

Constraints

  • The input must be a binary string of length 32.
  • 1 <= n <= 2^31 - 1 (for some test cases).

Examples

Example 1

Input
n = 00000000000000000000000000001011
Output
3

Example 2

Input
n = 00000000000000000000000010000000
Output
1

Example 3

Input
n = 11111111111111111111111111111101
Output
31

Approaches

1. Shift and check LSB

32 iterations: check n & 1, shift right.

Time
O(32)
Space
O(1)
function hammingWeight(n) {
  let count = 0;
  for (let i = 0; i < 32; i++) {
    count += (n & 1);
    n >>>= 1;
  }
  return count;
}

Tradeoff: Always 32 iterations regardless of how few bits are set.

2. Brian Kernighan's algorithm (optimal)

n & (n - 1) clears the lowest set bit. Iterate until n = 0; each iteration counts one bit.

Time
O(k) where k = set bits
Space
O(1)
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= n - 1;
    count++;
  }
  return count;
}

Tradeoff: Iterates only as many times as there are set bits. Best when most bits are 0.

Reddit-specific tips

Reddit interviewers grade on the n & (n - 1) trick. Bonus signal: mention that browsers and built-in CPUs often have a popcount instruction; in Node, Number.prototype.toString(2) + split + filter is a one-liner alternative but slow.

Common mistakes

  • Using >> instead of >>> — sign-extends and infinite-loops for negative-coerced n.
  • Forgetting n !== 0 termination.
  • Storing count outside the function (this is a pure function).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Counting bits 0..n (LC 338) — DP.
  • Hamming distance (LC 461) — popcount of (a ^ b).
  • How would you popcount a 64-bit integer?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why does n & (n - 1) clear the lowest set bit?

Subtracting 1 flips the lowest 1-bit to 0 and all lower 0-bits to 1. AND-ing clears them all and that one set bit.

When would you use a lookup table?

Precompute popcount for all 256 byte values; popcount(n) = sum of popcounts of its bytes. Useful in tight inner loops.

Practice these live with InterviewChamp.AI

Drill Number of 1 Bits and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →