Count Number of Set Bits / Hamming Weight
Solve this Problem
Given a non-negative integer
n, count how many bits in its binary representation are set to 1.
Checking all 32 bit positions works but does the same amount of work regardless of how many bits are actually set. Brian Kernighan's trick skips straight past the zeros: n & (n - 1) always clears exactly the lowest set bit, so repeating that step counts down to zero in exactly as many steps as there are set bits — no wasted checks on positions that were already 0.
Test Case 1:
Input:n = 11
Output:3
Explanation:11 = 1011 — three bits are set.
Test Case 2:
Input:n = 128
Output:1
Explanation:128 = 10000000 — a single set bit.
Test Case 3:
Input:n = 0
Output:0
Explanation:0 has no set bits.
Constraints
- ◆
0 ≤ n ≤ 2³¹ − 1
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Each of 32 Bits
BruteCheck every one of the 32 bit positions and tally how many are set. Correct, but this does the same fixed amount of work no matter how sparse or dense the set bits actually are.
Time
O(32)Space
O(1)Java
1class Solution {
2 public int countSetBits(int n) {
3 int count = 0;
4 for (int bit = 0; bit < 32; bit++) {
5 if (((n >> bit) & 1) == 1) {
6 count++;
7 }
8 }
9 return count;
10 }
11}Optimal — Brian Kernighan's Algorithm
Optimaln & (n - 1) always clears exactly the lowest set bit in n — subtracting 1 flips that bit and everything below it, and ANDing with the original keeps only what didn't change. Repeating that step counts down to zero in exactly as many steps as there are set bits, with no wasted checks on positions that are already 0.
Time
O(number of set bits)Space
O(1)Java
1class Solution {
2 public int countSetBits(int n) {
3 int count = 0;
4 while (n != 0) {
5 n = n & (n - 1);
6 count++;
7 }
8 return count;
9 }
10}