Pattern this teaches:Bit Manipulation
Number of 1 Bits
An easy Bit Manipulation interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Bit Manipulation
- Sheets
- 2
- Core for
- 9 roles
The problem
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Example 1
- Input
- n = 11 (binary: 00000000000000000000000000001011)
- Output
- 3
- Why
- The binary representation has three '1' bits at positions 0, 1, and 3.
Example 2
- Input
- n = 128 (binary: 00000000000000000000000010000000)
- Output
- 1
- Why
- Only one '1' bit at position 7.
Example 3
- Input
- n = 2147483645 (binary: 01111111111111111111111111111101)
- Output
- 30
- Why
- All bits except position 0 are set to 1, giving 30 '1' bits.
Constraints
- The input must be a binary string of length 32
How to think about it
Updated 2026-09-29Subtracting one from any non-zero binary number flips its lowest set bit to zero and turns all trailing zeroes below it into ones. Bitwise ANDing that predecessor back into the original value clears that single lowest set bit without disturbing any higher bits. Repeating this hops strictly from one set bit to the next.
Approaches, worst first
Test all thirty-two bit positions
time O(1) · space O(1)
Iterate through all thirty-two positions, masking each bit with a shifted mask or right-shifting n. Straightforward to write, but it performs thirty-two iterations even when n has only a solitary set bit.
Brian Kernighan bit clearingWrite this one
time O(k) · space O(1)
Repeatedly update n with n & (n - 1) and increment a counter until n becomes zero. Each step strips exactly one set bit, making the iteration count equal to the number of set bits rather than the total word width.
Where people lose marks · 2
- Using a signed right-shift operator instead of a logical unsigned right-shift operator causes an infinite loop on values with the highest sign bit set due to sign extension.
- Looping with a condition like `n > 0` breaks on 32-bit unsigned values whose sign bit is treated as negative in environments with signed 32-bit arithmetic; check `n !== 0` instead.
The theory behind it
Bit Manipulation — the ground this problem stands on. All Bit Manipulation problems
What Bit Manipulation is
Bit manipulation is the practice of working directly on the individual ones and zeros that form numbers in computer memory. Every integer is stored as a tiny row of electrical switches that are either on or off. Instead of running arithmetic loops, bitwise operations flip, mask, shift, or combine these switches in a single hardware cycle. This allows compact storage of sets and blazing-fast checks without allocating extra memory.
When to reach for it
Reach for bit manipulation when problems ask to find a unique non-duplicate number, count set bits, determine if a value is a power of two, or pack a set of small booleans into a single integer. Prompts mentioning constant O(1) auxiliary space constraints on array queries often hint at XOR cancellation. It is also the foundation of bitmask dynamic programming, where subsets of up to twenty items are tracked as integer masks.
How the pattern works
Think of an integer as a fixed-length set of flags. Use bitwise AND to inspect if a specific bit is set, bitwise OR to turn a bit on, and bitwise XOR to flip a bit or cancel out matched pairs. Learn the standard bit tricks: n AND with n minus one clears the lowest set bit, which counts ones quickly, while n AND with negative n isolates the lowest set bit. When packing sets into masks, represent the empty set as zero and add item i by shifting one left by i and combining with OR.
More Bit Manipulation problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .