Skip to main content

25. Number of 1 Bits

easyAsked at Ola

Count the set bits (Hamming weight) of an unsigned integer.

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

Problem

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Constraints

  • Input is an unsigned 32-bit integer

Examples

Example 1

Input
n = 00000000000000000000000000001011
Output
3

Example 2

Input
n = 11111111111111111111111111111101
Output
31

Approaches

1. Walk every bit

Check each of 32 positions for a 1.

Time
O(32)
Space
O(1)
let c = 0;
for (let i=0;i<32;i++) if ((n>>i)&1) c++;
return c;

Tradeoff:

2. Brian Kernighan trick

n & (n-1) clears the lowest set bit; count iterations until n is zero.

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

Tradeoff:

Ola-specific tips

Ola interviewers ask Brian Kernighan as a proxy for low-level fluency; tie it to counting active feature flags inside a packed driver-config bitmask.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →