← Back to DSA Animator
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.