191. Number of 1 Bits

mediumAsked at AMD

Count the number of set bits (population count) in a 32-bit integer. AMD treats this as a serious bit-manipulation signal — popcount is a hardware instruction (POPCNT in x86, vcnt in ARM) that appears in GPU shader parity checks, ECC implementations, sparse-matrix compression, and bitboard game AI. Knowing the Brian Kernighan trick separates candidates who understand bits from those who don't.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in AMD loops.

Glassdoor (2026-Q1)— AMD SWE and hardware-software co-design candidates report Number of 1 Bits as a very common problem with hardware POPCNT follow-up.
Blind (2025-11)— AMD interview threads flag this as a mandatory bit-manipulation problem for any AMD role touching compiler, driver, or firmware.

Problem

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Constraints

1 <= n <= 2^31 - 1

Examples

Example 1

Input

n = 11 (binary: 00000000000000000000000000001011)

Output

Explanation: Three bits are set: positions 0, 1, and 3.

Example 2

Input

n = 128 (binary: 00000000000000000000000010000000)

Output

Explanation: Only bit 7 is set.

Approaches

1. Bit shift loop

Check each of the 32 bits using n & 1, then right-shift. Count the set bits.

Time: O(32) = O(1)
Space: O(1)

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    count += n & 1;
    n >>>= 1; // unsigned right shift — treats n as unsigned 32-bit
  }
  return count;
}

Tradeoff: O(32) — iterates over all 32 bits. Simple. Use `>>>` (unsigned right shift) in JS so that the sign bit is shifted in as 0, not 1 for negative numbers.

2. Brian Kernighan trick

n & (n-1) clears the lowest set bit of n. Count how many times you can do this before n becomes 0 — that count is the number of set bits.

Time: O(k) where k = number of set bits
Space: O(1)

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= (n - 1); // clear the lowest set bit
    count++;
  }
  return count;
}

Tradeoff: O(k) — only iterates as many times as there are set bits. For sparse integers (few set bits), this is dramatically faster than the 32-iteration loop. This is the expected AMD answer.

3. Parallel bit summation (SWAR popcount)

Use bitwise arithmetic to sum adjacent bit groups in parallel — a technique that mirrors how hardware POPCNT instructions work at the gate level.

Time: O(1) — constant number of operations
Space: O(1)

function hammingWeight(n) {
  n = n - ((n >>> 1) & 0x55555555);
  n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
  n = (n + (n >>> 4)) & 0x0f0f0f0f;
  n = (n * 0x01010101) >>> 24;
  return n;
}

Tradeoff: Constant time, constant ops — this is effectively how x86 POPCNT hardware works internally. Mentioning this at AMD is a strong signal of hardware-software boundary awareness.

AMD-specific tips

At AMD this problem is almost always a gateway to a hardware discussion. After solving it, expect follow-ups: 'Does x86 have a hardware instruction for this?' (yes — POPCNT, available since SSE4.2), 'How many clock cycles does POPCNT take?' (typically 3 cycles latency on modern AMD Zen CPUs), 'When would you use the software popcount vs the hardware instruction?' The Brian Kernighan trick is the canonical software answer. The SWAR approach demonstrates you understand the hardware implementation. Both matter at AMD.

Common mistakes

Using `>>` (signed right shift) instead of `>>>` (unsigned) in JS — for negative n, >> fills with 1s and the loop never terminates.
Not handling n=0 edge case — Brian Kernighan: the while loop exits immediately for n=0, returning 0. Correct.
Thinking n & (n-1) clears the highest bit — it clears the LOWEST set bit. Subtracting 1 flips all bits from the lowest set bit downward.
Using a 64-bit loop when the problem specifies 32-bit integers — cap at 32 iterations.

Follow-up questions

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

Counting Bits (LC 338) — compute popcount for all numbers 0..n using DP.
Reverse Bits (LC 190) — reverse the 32-bit representation.
What is the POPCNT instruction on AMD Zen 4, and what is its latency/throughput?

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 all bits from the lowest set bit position downward (including that bit itself). ANDing with the original n then zeros out those flipped bits, leaving all higher bits unchanged and the lowest set bit cleared.

When is the bit-shift loop better than Brian Kernighan?

When the number is dense with set bits (e.g., 0xFFFFFFFF), both iterate 32 times. Brian Kernighan is better for sparse integers. For AMD hardware integers like GPU thread masks or SIMD lane enables, both are equally fast in practice since hardware POPCNT makes the software implementation irrelevant for hot paths.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →