Skip to content

Volume ITechnology

4.30.2 — Number of 1 Bits ​

LeetCode 191 · Easy · ★ Blind 75

The problem ​

Count the set bits in a 32-bit unsigned integer. This count is called the Hamming weight, or the population count.

n = 11    (binary 1011)         →  3
n = 128   (binary 10000000)     →  1

The obvious solution ​

Check each of the 32 bits:

python
count = 0
for i in range(32):
    if n & (1 << i):
        count += 1
return count

O(32), which is constant — and it does the same work whether n has one set bit or thirty-two.

The better idiom ​

python
while n:
    n &= n - 1        # clears the LOWEST set bit
    count += 1

This is Brian Kernighan's method, and the loop runs exactly as many times as there are set bits. For n = 128 that is one iteration instead of thirty-two.

Why n & (n - 1) clears the lowest set bit. Subtracting 1 borrows: the lowest 1 becomes 0, and every 0 below it becomes 1. Everything above is untouched. ANDing with the original therefore keeps only the bits above the lowest 1.

n       = 1011 0100
n - 1   = 1011 0011      ← lowest 1 flipped, zeros below became 1
n & (n-1) = 1011 0000    ← that bit gone

Understand this rather than memorising it. It also gives you the power-of-two test — n > 0 and n & (n - 1) == 0, since a power of two has exactly one set bit and clearing it leaves zero.

The solution ​

python
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0  # (1)
        while n:  # (2)
            n &= n - 1              # (3) clear the lowest set bit
            count += 1  # (4)
        return count  # (5)
ts
function hammingWeight(n: number): number {
  let count = 0;  // (1)
  while (n !== 0) {  // (2)
    n &= n - 1;  // (3)
    count++;  // (4)
  }
  return count;  // (5)
}

Line by line ​

(1) The number of 1 bits found so far.

(2) Keep going while n still has any 1 bit.

(3) Remove the lowest 1 bit. Subtracting 1 from a number flips its lowest 1 bit to 0 and turns every 0 below it into 1. For example, 1100 minus 1 is 1011. Then & (AND) keeps only the bits that are 1 in both: 1100 & 1011 = 1000. The lowest 1 bit is gone, and everything else is unchanged.

(4) Count it.

(5) The loop ran once for each 1 bit, so count is the answer. It never looks at the 0 bits, which is why this is faster than checking all 32 positions.

Trace ​

Take n = 11, which is 1011 in binary.

Stepn (binary)n − 1n & (n − 1)count
11011101010101
21010100110002
31000011100003

Three 1 bits.

In JavaScript, n must stay non-negative for the while (n !== 0) test. Bitwise operators coerce to 32-bit signed integers, so a value with the top bit set becomes negative and the loop still terminates correctly — because n &= n - 1 strictly reduces the number of set bits regardless of sign. Worth checking rather than assuming.

In Python, negative inputs would loop forever, since Python integers have infinitely many leading 1s. The problem gives an unsigned value, so it does not arise — but it is the kind of assumption to state.

Edge cases ​

  • n = 0. The loop never runs, and the answer is 0.
  • All 32 bits set. The loop runs 32 times.

Complexity ​

O(\text{number of set bits}), at most 32. O(1) space.

The three faster methods ​

Worth naming, in increasing order of cleverness.

A lookup table. Precompute the count for all 256 byte values, then sum four lookups per 32-bit integer. O(1) with four memory accesses, and it is what many libraries did before hardware support.

The SWAR trick. A sequence of masked shifts and adds counts bits in parallel within the word — pairs, then nibbles, then bytes — in about twelve operations with no loop and no table. Elegant and unmemorable; know it exists.

The hardware instruction. Modern CPUs have POPCNT, and compilers emit it for __builtin_popcount in C, Integer.bitCount in Java, and int.bit_count() in Python 3.10+. In real code, use the built-in.

bin(n).count('1') in Python is also perfectly acceptable and often the fastest thing you can write — but in an interview, write the loop, since the loop is what is being asked about.

Where this goes next ​

  • Counting Bits — the count for every number from 0 to n, where DP beats calling this function repeatedly. 4.30.3.
  • Hamming Distance — the number of differing bits between two numbers, which is popcount(x ^ y). One line, and it is the foundation of error-correcting codes (Chapter 1.8).
  • Bitmask DP — the population count of a mask tells you how many items a subset holds, which is often part of the DP state.
  • Power of Two — n > 0 and n & (n - 1) == 0.

What the interviewer will push on ​

"Explain n & (n - 1)." The borrow argument. This is the question.

"How many iterations does your loop run?" Once per set bit, not 32.

"How would you test for a power of two?" The same idiom, and say why.

"What is the fastest way in production?" The built-in, which compiles to a single instruction.

"What about negative numbers?" In Python the loop would never end; in JavaScript the 32-bit coercion keeps it finite. Naming your language's behaviour is the answer.

One thing to volunteer: derive the idiom on a small binary number out loud. It takes fifteen seconds and it converts a memorised trick into something you obviously understand.

Next: 4.30.3 Counting Bits — the same count for every number up to n, in one pass.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet