Practice › Bit Manipulation
Count Set Bits
Easy · Bit Manipulation · Asked at Amazon, Microsoft, Cisco, TCS, Infosys
Print the number of 1 bits in the binary representation of n.
Input
One integer n.
Output
The number of set bits.
Constraints
- 0 ≤ n ≤ 10^18
n & (n − 1)removes the lowest set bit.
Example 1
Input
11
Output
3
Example 2
Input
128
Output
1
Hints
- Checking all 64 bits works. Can you loop only as many times as there are 1 bits?
- n & (n − 1) clears the lowest set bit. Count how many times you can do that before n becomes 0.
Approach
Brian Kernighan's trick: subtracting 1 flips the lowest set bit and every 0 below it, so n & (n − 1) removes exactly that lowest 1. Repeat until n is 0 and count the steps. That's one iteration per set bit. Built-ins exist too: __builtin_popcountll, Long.bitCount, bin(n).count("1").
Complexity: O(number of set bits) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
int count = 0;
while (n) {
n &= n - 1; // clear the lowest set bit
count++;
}
cout << count << "\n";
return 0;
}Python solution
n = int(input())
count = 0
while n:
n &= n - 1 # clear the lowest set bit
count += 1
print(count)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
int count = 0;
while (n != 0) {
n &= n - 1; // clear the lowest set bit
count++;
}
System.out.println(count);
}
}