Skip to main content

191. Number of 1 Bits

easyAsked at Intel

Count the number of '1' bits in an unsigned 32-bit integer (the Hamming weight). Intel asks because the n & (n-1) trick reveals whether you've internalized bit-arithmetic identities, and because POPCNT is a real CPU instruction Intel ships — the candidate who knows the hardware path is the senior signal.

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

Source citations

Public interview reports confirming this problem appears in Intel loops.

  • Glassdoor (2026-Q1)— Intel SWE phone-screen reports recurring 'count set bits' question, often paired with reverse-bits.
  • GeeksforGeeks (2025-09)— Intel hardware-engineering interview archive lists Hamming weight as a standard ask.
  • Reddit r/cscareerquestions (2025-11)— Intel new-grad SWE thread references 'count 1 bits' as a 10-minute 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.
  • 0 <= n <= 2^31 - 1 (signed-32 interpretation in JS).

Examples

Example 1

Input
n = 00000000000000000000000000001011
Output
3

Explanation: The input binary string has a total of three '1' bits.

Example 2

Input
n = 00000000000000000000000010000000
Output
1

Example 3

Input
n = 11111111111111111111111111111101
Output
31

Approaches

1. Bit-by-bit scan (brute force)

Loop 32 times. On each iteration, check the lowest bit and right-shift.

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

Tradeoff: Always 32 iterations regardless of how many bits are set. Easy to write, easy to verify, but wastes cycles on sparse inputs.

2. Brian Kernighan trick (optimal)

Repeatedly clear the lowest set bit via n &= n - 1 until n is zero. Each clear costs one operation, so total work is exactly popcount(n).

Time
O(k) where k = number of set bits
Space
O(1)
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1); // clears the lowest set bit
    count++;
  }
  return count;
}

Tradeoff: Work scales with the population count instead of with the word width. For sparse inputs (k << 32) this is a real speedup. The trick is also one of the most-recognized bit-arithmetic identities — articulating it earns the senior signal.

Intel-specific tips

Intel interviewers will probe whether you know POPCNT (the SSE4.2 instruction that does this in 1 cycle). Mentioning '__builtin_popcount in GCC or _mm_popcnt_u32 maps to the POPCNT instruction on any Intel CPU from Nehalem onward' lands as senior-IC awareness. Even though the LeetCode rubric doesn't compile to native, the awareness signals you've shipped performance-critical C/C++.

Common mistakes

  • Using signed right-shift (>>) instead of unsigned (>>>). For inputs with the sign bit set, the sign gets dragged and the loop never terminates.
  • Writing n & (n - 1) but forgetting to assign — `n & (n - 1)` doesn't mutate n; you need `n = n & (n - 1)` or `n &= n - 1`.
  • Quoting Big-O as O(n) — the input bit-width is fixed at 32 so it's O(1); the per-bit work is O(k) where k = popcount.

Follow-up questions

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

  • Hamming Distance (LC 461) — popcount of (x XOR y).
  • Counting Bits (LC 338) — return popcount for every i in [0, n] using DP: dp[i] = dp[i >> 1] + (i & 1).
  • If hammingWeight runs in a hot loop, what's the optimal implementation? (Hardware POPCNT instruction; or a 256-entry byte lookup table.)

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 from n flips the lowest set bit to 0 and turns every lower bit (which were all 0) into 1. ANDing back with n keeps only the bits above the lowest set bit unchanged and zeros out the lowest set bit and everything below it.

Is the Brian Kernighan version always faster?

Only when the popcount is less than 32. For inputs with most bits set (popcount near 32), the loop runs nearly 32 times anyway and the trick offers no speedup. In practice it's a net win because real-world bitmaps are sparse.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →