Skip to main content

26. Number of 1 Bits

easyAsked at Datadog

Count the number of 1-bits in an unsigned 32-bit integer (popcount). Datadog asks this for the Brian Kernighan trick — used in their bitmap-based tag-presence checks where popcount is in the hot path.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — graded on Brian Kernighan.
  • LeetCode Discuss (2025-10)— Recurring bit-manipulation question.

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.

Examples

Example 1

Input
n = 00000000000000000000000000001011
Output
3

Example 2

Input
n = 11111111111111111111111111111101
Output
31

Approaches

1. Loop through all 32 bits

Mask each bit, count if set.

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

Tradeoff: Always 32 iterations regardless of how many bits are set. Slower in the common case where most bits are 0.

2. Brian Kernighan's algorithm (optimal)

n & (n-1) clears the lowest set bit. Loop until n is 0; iterations = popcount.

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

Tradeoff: Only as many iterations as there are set bits. Datadog-canonical: in sparse bitmaps (common case), this is far faster.

Datadog-specific tips

Datadog interviewers know the trick — they're checking whether you recognize n & (n-1) clears the lowest set bit. Articulate why before coding. Mention SWAR (SIMD within a register) for the absolute-fastest fixed-width popcount.

Common mistakes

  • Forgetting that JS bitwise ops are 32-bit signed — for unsigned interpretation, use >>> 0 if needed.
  • Doing n = n / 2 instead of n >>> 1 — division on floats vs proper bit shift.
  • Looping while n > 0 instead of n != 0 — fails for inputs with the sign bit set.

Follow-up questions

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

  • Reverse Bits (LC 190) — companion bit-manipulation problem.
  • Counting Bits (LC 338) — popcount for all 0..n.
  • Hamming Distance (LC 461) — XOR + popcount.

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 set bit to 0 and all lower zero bits to 1. ANDing with n keeps the higher bits unchanged but zeroes the previously-lowest-set bit.

Can we go faster than O(popcount)?

Yes — SWAR popcount runs in O(log n) via parallel summation. Modern CPUs have a POPCNT instruction; in JS you'd write the SWAR sequence manually.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →