Skip to main content

25. Number of 1 Bits

easyAsked at Snowflake

Count the number of 1 bits in an integer (popcount). Snowflake uses this to test bit-manipulation knowledge and to set up a follow-up on bitmap-index intersection — popcount is the hot loop in bitmap predicate evaluation.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake execution-engine team uses this to set up bitmap-index follow-up.
  • LeetCode Discuss (2025-09)— Reported at Snowflake new-grad screens.

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 = 00000000000000000000000010000000
Output
1

Approaches

1. Bit-by-bit shift

Loop 32 times, test LSB, shift right.

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

Tradeoff: Works, always 32 iterations regardless of input.

2. Brian Kernighan's trick (optimal)

Repeatedly do n = n & (n - 1) — this clears the lowest set bit. Count iterations until n == 0.

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

Tradeoff: Loops only popcount times — fast for sparse 1-bits. The classic 'clear lowest set bit' identity.

Snowflake-specific tips

Snowflake interviewers want Brian Kernighan's trick and the explanation of why n & (n-1) clears the lowest set bit. Bonus signal: discuss popcount hardware instructions (POPCNT on x86, vcnt on ARM) and their role in vectorized bitmap-index intersection in their executor.

Common mistakes

  • Forgetting that >>> is needed (not >>) for JS unsigned shift.
  • Stopping the loop on the wrong condition (e.g., when n is small instead of zero).
  • Using string conversion (toString(2).split('1').length - 1) — works but defeats the purpose.

Follow-up questions

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

  • Counting Bits (LC 338) — compute popcount for 0..n efficiently using DP.
  • Hamming Distance (LC 461) — popcount of XOR.
  • How does Snowflake's bitmap-index intersect predicates?

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 bits to 1. ANDing with the original keeps the higher bits and clears that lowest set bit plus the trailing 1s — net effect: lowest set bit is gone.

How does popcount help bitmap indexes?

Snowflake (and column stores in general) use bitmap-style structures for predicate evaluation. After ANDing multiple predicate bitmaps, popcount of the result equals the number of matching rows — and it's a single SIMD instruction.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →