How do you count the number of set bits in an integer?

Q: How do you count the number of set bits in an integer?

**Target Audience:** Developers preparing for coding interviews who know loops and integers in Python; binary is explained as we go. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A night guard walks past an office tower and wants to know how many windows are lit. The slow way is to look at every single window, lit or dark, floor by floor. A sharper guard notices a pattern: if he could jump straight from one lit window to the next and skip the dark ones, the walk would take as many steps as there are lights, not as many as there are windows. An integer

The problem

Question presented to candidate: "Write a Python function that returns the number of 1 bits in an integer. Start simple, then make it faster, and tell me what your function returns for a negative number."

What a strong answer should cover:

The naive loop over 32 bit positions, then Brian Kernighan's n &= n - 1, which runs once per set bit.
Constant-time options: a 256-entry byte table, or the parallel SWAR additions.
Complexity: O(32) vs O(number of set bits) vs O(1), and the O(n) DP bits[i] = bits[i >> 1] + (i & 1) for every number 0..n.
Python details: int.bit_count() (Python 3.10+) and bin(n).count("1"); Python ints are unbounded, so a negative number has no fixed bit pattern: while n: n &= n - 1 never ends for negative n, and you mask with n & 0xFFFFFFFF to get the 32-bit answer.

Clarifying questions expected:

How should negative numbers be treated: as 32-bit two's complement, or by magnitude?
Is this one call, or many calls (or every number up to n)?

Code / implementation expected: Yes — Kernighan's loop in Python 3 with a 32-bit mask, plus the built-in int.bit_count().

bit-manipulation

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers preparing for coding interviews who know loops and integers in Python; binary is explained as we go.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A night guard walks past an office tower and wants to know how many windows are lit. The slow way is to look at every single window, lit or dark, floor by floor. A sharper guard notices a pattern: if he could jump straight from one lit window to the next and skip the dark ones,

The solution is hidden so you can try first

13 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonNaive vs Kernighan vs table vs SWAR vs built-in

Practice

PythonBits of every number 0..n with DP, and work counters

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.