โ† Adobe questions

Calculate number of set bits

Filed under Adobe

Free read 1 of 3

Understand 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

  1. Understand the input range and whether built-in functions like `bin().count('1')` are permitted.

Solution

O(K) time where K is set bits, O(1) space

Python
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.