Skip to main content

26. Number of 1 Bits

easyAsked at Workday

Return the number of set bits in a 32-bit unsigned integer. Workday uses this to count active permissions in a role bitmap — bonus signal if you know the n & (n-1) trick.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2025)— Workday RBAC team.

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

  • The input must be a binary string of length 32.
  • Follow-up: If this function is called many times, how would you optimize it?

Examples

Example 1

Input
n = 00000000000000000000000000001011
Output
3

Example 2

Input
n = 11111111111111111111111111111101
Output
31

Approaches

1. Iterate all 32 bits

For each of 32 bits, AND with 1 and increment if set.

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

Tradeoff: Works in constant time but always 32 iterations regardless of how few bits are set.

2. Brian Kernighan's bit clear

Repeatedly do n &= (n-1) — each iteration clears the lowest set bit. Loop until n is 0.

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

Tradeoff: Stops as soon as no bits are left. The n & (n-1) idiom is the canonical bit-counting trick.

Workday-specific tips

Workday wants the n & (n-1) trick. Walk through why: n-1 flips the lowest set bit and all the zeros below it; ANDing with n preserves the rest and clears the low bit. Mention RBAC bitmap counts.

Common mistakes

  • Using >> instead of >>> — sign bit pollutes high bits if you shift a negative.
  • Looping a fixed 32 times even when n is small — wastes work.
  • Not knowing why n & (n-1) clears the lowest set bit.

Follow-up questions

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

  • Counting Bits (LC 338) — for all i in [0, n].
  • Hamming Distance (LC 461).
  • Power of Two (LC 231) — exactly one set bit.

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?

n-1 flips the lowest 1 to 0 and turns every bit below it from 0 to 1. ANDing with n: the lowest 1 becomes 0 (1 & 0); the bits below stay 0 (0 & 1); bits above are unchanged.

Built-in?

Some languages have popcount. JS doesn't — though you can hack it via BigInt.toString(2). Bring the trick.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →