Skip to main content
DSA patterns

Number of 1 Bits

easyBits Must-doCiscoDellTCS

Problem statement

You're given a positive integer n. Count how many of the bits in its binary representation are set to 1 — this count is also known as the number's Hamming weight.

For example, the number 11 is 1011 in binary, which has three 1s in it.

Examples

Example 1

Input: n = 11

Output: 3

Explanation: 11 in binary is 1011, which has three set bits.

Example 2

Input: n = 128

Output: 1

Explanation: 128 in binary is 10000000 — a single set bit, way out at the front.

Example 3

Input: n = 2147483645

Output: 30

Explanation: 2147483645 in binary is 1111111111111111111111111111101, a 31-bit pattern with thirty 1s and one 0.

Hints

Hint 1: You can check whether the lowest bit of a number is 1 with n & 1, and drop that bit by shifting the number right by one.

Approach

Optimal: Byte lookup table

Intuition

This is the direct answer to the problem's own follow-up: "if this function is called many times, how would you optimize it?" Precompute, just once, the set-bit count for every possible byte value (0 through 255) into a small table. Any 32-bit number splits cleanly into four 8-bit chunks; look each chunk up in the table and add the four results together. After the one-time cost of building the 256-entry table, every future call is just four array reads and three additions — no bit-by-bit looping at all.

Steps

  1. Build a table of 256 entries where table[i] holds the number of set bits in the 8-bit value i — built once, ahead of time, and reused for every call.
  2. Split n into four 8-bit chunks using masking and shifting: n & 0xFF (lowest byte), (n >> 8) & 0xFF, (n >> 16) & 0xFF, and (n >> 24) & 0xFF (highest byte).
  3. Look up each chunk's set-bit count in the table.
  4. Add the four looked-up counts together and return the sum.

Dry run

n = 128 (binary 00000000 00000000 00000000 10000000)

chunk value table lookup
byte 0 (bits 0–7) 128 1
byte 1 (bits 8–15) 0 0
byte 2 (bits 16–23) 0 0
byte 3 (bits 24–31) 0 0

Sum: 1 + 0 + 0 + 0 = 1, matching the example.

Edge cases: n = 2147483645 still splits cleanly into exactly four bytes and returns the correct sum (30) in the same fixed four lookups, even though it has far more set bits than the earlier examples.

Complexity

Time O(1) - every call does exactly four table lookups and three additions, regardless of how many bits `n` has set, since a 32-bit integer always splits into exactly four 8-bit chunks.

Space O(1) - the lookup table has a fixed size of 256 entries, built once, independent of `n`.

class Solution:
    _table = None

    @classmethod
    def _build_table(cls):
        table = [0] * 256
        for i in range(1, 256):
            table[i] = (i & 1) + table[i >> 1]
        cls._table = table

    def hammingWeight(self, n):
        if Solution._table is None:
            Solution._build_table()
        table = Solution._table
        return (
            table[n & 0xFF]
            + table[(n >> 8) & 0xFF]
            + table[(n >> 16) & 0xFF]
            + table[(n >> 24) & 0xFF]
        )


if __name__ == "__main__":
    print(Solution().hammingWeight(11))
    print(Solution().hammingWeight(128))
    print(Solution().hammingWeight(2147483645))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "count the 1 bits in a number's binary representation" (Hamming weight)
  • Idea: n & (n-1) clears the lowest set bit each time — count how many times you can do that before n hits 0; for repeated calls, precompute a small lookup table instead
  • Cost: O(log n) time, O(1) space for both bit-by-bit approaches; O(1) time, O(1) space per call with a precomputed byte lookup table
  • Trap: checking every bit position one at a time when the number has very few set bits — Brian Kernighan's trick skips straight from one set bit to the next instead

Interview follow-ups

  • The function really is called many times in a tight loop — does the table rebuild every call hurt performance?

    No, as long as the table is built once and reused — that's the whole point of the optimization. The Python, Java and C++ versions above all guard the table-building step so it only runs the first time hammingWeight is called; every call after that is just the four lookups and three additions, with no rebuilding.

  • What if you need the count for arbitrarily large numbers (bigger than 32 or 64 bits), not fixed-width integers?

    The byte-chunking trick still works, but now the number of chunks grows with the size of the number instead of staying fixed at four. Split the big number into as many 8-bit (or wider) chunks as it takes to cover it, look each one up in the same 256-entry table, and sum them — this becomes O(k) where k is the number of chunks, rather than the true O(1) of the fixed-width version.

Frequently asked questions

Subtracting 1 flips every bit from the lowest set bit down to the end: that bit turns to 0, and every 0 bit below it turns to 1 (this is the same "borrow" that happens in ordinary subtraction). ANDing the original number with that result keeps every bit above the lowest set bit unchanged (since those bits are identical in both numbers), while the lowest set bit and everything below it becomes 0 either way. The net effect is exactly one bit removed.

Both are O(log n) in the worst case, so the improvement isn't in the big-O ceiling — it's in the typical case. The brute-force loop always runs once per bit position (up to 32 times for a 32-bit integer), even when most of those bits are 0. Brian Kernighan's algorithm only loops once per set bit, so a number like 128 (only one set bit) finishes in a single iteration instead of eight.

Counting set bits shows up in real systems work — computing Hamming distance between IP masks, tallying flags packed into a bitmask, or checking parity in low-level protocols. When a function like this runs in a hot path (called on every packet, every request, or every log line), moving the cost from "per call" to "once, ahead of time" is exactly the kind of precomputation trade-off that shows up when optimizing throughput-sensitive code.

A lookup table needs one entry for every possible input value. A table for all 32-bit numbers would need 2³² entries — far too much memory. Splitting into four bytes means the table only needs 2⁸ = 256 entries, small enough to build instantly and keep entirely in a CPU cache, while still answering any 32-bit number's count in a fixed four lookups.