DSA AnimatorDSA animations
Number of 1 Bits LC #191 Easy Bit Manipulation · Kernighan
Problem

Given a positive integer n, return the number of set bits in its binary representation (also known as the Hamming weight).

Example 1
Input: n = 11
Output: 3
Explanation: 11 = 0b1011 has three set bits.
Example 2
Input: n = 128
Output: 1
Explanation: 128 = 0b10000000 has exactly one set bit.
Constraints: 1 ≤ n ≤ 2³¹ − 1
Try Examples
Custom:
Approach
Kernighan's Bit Trick — n &= (n−1)
n & (n-1) clears the rightmost set bit. Count iterations until n = 0. Runs exactly k times where k is the number of set bits — much faster than checking every bit.
Binary Representation of n
Bits (MSB → LSB)
n = —
Variables
n (decimal)
—
count
0
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
n & (n−1) clears the rightmost set bit in a single operation
2
Each iteration removes exactly one 1-bit from n
3
Loop runs exactly k times where k = number of set bits
4
Faster than checking every bit position individually
Time
O(k)
Space
O(1)
Why It Works

The expression n & (n−1) always clears the lowest set bit of n. This is because subtracting 1 from n flips all bits from the lowest set bit down to bit 0 (turning that set bit into 0 and all lower 0-bits into 1s). The AND then cancels out all those flipped bits. By repeating until n becomes 0, we count exactly how many set bits existed — one per iteration. Brian Kernighan's trick runs in O(k) where k is the popcount, not O(log n) like a naive bit-by-bit scan.

How to solve Number of 1 Bits

LeetCode 191 · Easy · Bit Manipulation · Pattern: Brian Kernighan

Why the obvious approach is slow

You can check all 32 bits one by one with a shift and a mask. That always takes 32 steps, even when only a few bits are set.

The key idea

Look at n −1 in binary: the lowest 1 bit of n turns into 0, and every bit below it turns into 1. So n AND n −1 is n with its lowest set bit removed. Repeat until n becomes 0, counting each step. The loop runs exactly once per 1 bit.

Remember

N AND n −1 removes the lowest set bit. This trick appears in many bit problems.

Run the animation above on your own input, or watch the 1:26 video explanation of Number of 1 Bits with a dry run and Java code.

More Bit Manipulation problems