DSA interview question

Count the Number of Set Bits

Easy · Algorithms · Topics: bit manipulation

The problem

A feature-flag service stores which of 32 experiments a user is enrolled in as bits of an integer, and analytics dashboards constantly ask "how many experiments is this user in?", meaning how many bits are set. Checking all 32 bits one at a time works. Brian Kernighan's trick is neater: n & (n − 1) clears the lowest set bit, so repeating it until n is 0 takes exactly as many steps as there are set bits.

Example: 6 (110) → 2; 255 → 8.

Function signature

int countSetBits(int n);  // counts 1s in the 32-bit two's complement representation

Test cases

Input	Output	Explanation
`6`	`2`	110
`8`	`1`	1000
`0`	`0`
`255`	`8`	11111111
`2147483647`	`31`	INT_MAX
`-1`	`32`	All 32 bits are set

(Confirm: negatives are counted in 32-bit two's complement.)

How interviewers phrase it

"Count the number of 1 bits in an integer" (LeetCode 191 "Number of 1 Bits", GeeksforGeeks "Set Bits").
Follow-up: "count the bits of every number from 0 to n" (LeetCode 338).

Clarifying questions to ask

Signed or unsigned input? How should negatives be counted?
Is this called once or many times? (Many calls may justify a lookup table.)
Can I use built-ins like __builtin_popcount?

Follow-ups to expect

"Why does Kernighan's loop work?"
"Simple alternative?"
"Faster for many queries?"
"Counting bits for 0..n?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview