# The Bit Counter

> How many lights are on in the binary representation?

Canonical URL: <https://datadriven.io/problems/the_bit_counter>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a non-negative integer n, return the number of 1-bits in its binary representation. Do not convert to a binary string; use bitwise operations.

## Worked solution and explanation

### Why this problem exists in real interviews

Counting set bits without string conversion tests **bitwise operations**: right-shift and AND masking. It is a fundamental low-level operation that reveals whether you understand binary representation.

> **Trick to Solving**
>
> Use `n & 1` to check the lowest bit, then right-shift with `n >>= 1`. Repeat until n is 0. Each iteration peels off one bit.

---

### Break down the requirements

#### Step 1: Check the lowest bit

`n & 1` is 1 if the lowest bit is set, 0 otherwise.

#### Step 2: Right-shift to expose the next bit

`n >>= 1` moves all bits one position to the right, discarding the lowest.

#### Step 3: Repeat until n is 0

When all bits have been shifted out, the count is complete.

---

### The solution

**Bit-by-bit counting with shift and mask**

```python
def count_bits(n):
    count = 0
    while n > 0:
        count += n & 1
        n >>= 1
    return count
```

> **Time and Space Complexity**
>
> **Time:** O(log n) since the number of bits in n is proportional to log n.
> 
> **Space:** O(1). A single counter.

> **Interviewers Watch For**
>
> Using `n & 1` and `n >>= 1` rather than converting to `bin(n)` and counting '1' characters. The bitwise approach is what interviewers want to see.

> **Common Pitfall**
>
> Using `bin(n).count('1')`. While correct, it converts to string and defeats the purpose of the bitwise exercise.

---

## Common follow-up questions

- Can you count bits in O(number of set bits) time? _(Tests Brian Kernighan's algorithm: `n &= (n - 1)` clears the lowest set bit each iteration.)_
- How would you handle negative numbers? _(Tests understanding of two's complement. In Python, negative integers have infinite precision, so you would need to mask to a fixed width.)_
- How would you count bits for all numbers from 0 to n? _(Tests the DP approach: `bits[i] = bits[i >> 1] + (i & 1)` for building a lookup table.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_bit_counter)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.