Calculate number of set bits
Filed under Adobe
Free read 1 of 3Understand the input range and whether built-in functions like `bin().count('1')` are permitted.
The question
Find the most optimal way to calculate the number of set bits (population count) in a given integer.
Constraints
- The integer can be positive or negative (represented in standard 32-bit or 64-bit two's complement).
- Time complexity should scale with the number of set bits rather than the total number of bits.
Examples
- Input
- n = 9
- Output
- 2
- Why
- Binary representation of 9 is 1001, which has 2 set bits.
Approach
Understand the input range and whether built-in functions like `bin().count('1')` are permitted.
Iterate through all 32 bits of the integer using a bitmask and check if each bit is set.
Use Brian Kernighan's algorithm: `n & (n - 1)` clears the least significant set bit in each iteration. The loop runs exactly as many times as there are set bits.
Handle 0 and negative integers where sign extension might affect bitwise operations.
Solution
O(K) time where K is set bits, O(1) space
def countSetBits(n):
count = 0
n &= 0xFFFFFFFF
while n:
n &= (n - 1)
count += 1
return count
Tips
- What they are testing: Test with 0, negative numbers, maximum integer values, and powers of two.
- Common mistake: Using a naive loop that checks all 32/64 bits even when the number is small, instead of Brian Kernighan's algorithm.
Related Adobe questions
Collected from public candidate posts and coding forums. Updated Nov 2026.