Learn Count Set Bits — Free DSA Tutorial

Set Bit Meaning

A 'set bit' simply means a bit whose value is 1 rather than 0 — counting set bits means counting how many 1s appear in a number's binary representation, sometimes called its 'population count'.

Example: Set Bit Meaning

#include <iostream>
using namespace std;
int main() {
	int n = 11;
	cout << n << " (binary 1011) has 3 set bits -- its population count is 3";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11;
		System.out.println(n + " (binary 1011) has 3 set bits -- its population count is 3");
	}
}

n = 11
print(f"{n} (binary 1011) has 3 set bits -- its population count is 3")

#include <stdio.h>
int main() {
	int n = 11;
	printf("%d (binary 1011) has 3 set bits -- its population count is 3", n);
	return 0;
}

Loop Method

The most direct method checks each bit position one at a time (shifting and masking, or dividing and taking remainders repeatedly), incrementing a counter every time a 1 bit is found, which takes time proportional to the number of bits in the value.

Example: Loop Method

#include <iostream>
using namespace std;
int main() {
	int n = 11, count = 0;
	while (n) { count += n & 1; n >>= 1; }
	cout << "Set bits counted by checking each position: " << count;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11, count = 0;
		while (n != 0) { count += n & 1; n >>= 1; }
		System.out.println("Set bits counted by checking each position: " + count);
	}
}

n = 11
count = 0
while n:
    count += n & 1
    n >>= 1
print("Set bits counted by checking each position:", count)

#include <stdio.h>
int main() {
	int n = 11, count = 0;
	while (n) { count += n & 1; n >>= 1; }
	printf("Set bits counted by checking each position: %d", count);
	return 0;
}

Brian Kernighan Method

Brian Kernighan's trick computes n & (n - 1), which always clears exactly the lowest set bit of n; repeating this and counting how many times it takes to reach zero counts the set bits directly, doing work proportional only to the number of 1 bits rather than the total bit width.

Example: Brian Kernighan Method

#include <iostream>
using namespace std;
int main() {
	int n = 11, count = 0;
	while (n) { n &= (n-1); count++; }
	cout << "n & (n-1) clears lowest set bit each time, iterations = " << count;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11, count = 0;
		while (n != 0) { n &= (n-1); count++; }
		System.out.println("n & (n-1) clears lowest set bit each time, iterations = " + count);
	}
}

n = 11
count = 0
while n:
    n &= (n-1)
    count += 1
print("n & (n-1) clears lowest set bit each time, iterations =", count)

#include <stdio.h>
int main() {
	int n = 11, count = 0;
	while (n) { n &= (n-1); count++; }
	printf("n & (n-1) clears lowest set bit each time, iterations = %d", count);
	return 0;
}

Language Helpers

Many languages provide a built-in, hardware-accelerated function for this exact operation (like __builtin_popcount in C++ or Integer.bitCount in Java), which is typically faster than any hand-written loop.

Example: Language Helpers

#include <iostream>
using namespace std;
int main() {
	int n = 11;
	cout << "__builtin_popcount(" << n << ") = " << __builtin_popcount(n);
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int n = 11;
		System.out.println("Integer.bitCount(" + n + ") = " + Integer.bitCount(n));
	}
}

n = 11
print(f"bin(n).count('1') = {bin(n).count('1')}")

#include <stdio.h>
int main() {
	int n = 11;
	printf("__builtin_popcount(%d) = %d", n, __builtin_popcount(n));
	return 0;
}

Practice

Counting set bits shows up in problems involving subsets (since a bitmask's set-bit count tells you the subset's size), checksums, and various bit-manipulation puzzles that ask about the weight of a binary number.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "A bitmask's set-bit count tells you the represented subset's size";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("A bitmask's set-bit count tells you the represented subset's size");
	}
}

print("A bitmask's set-bit count tells you the represented subset's size")

#include <stdio.h>
int main() {
	printf("A bitmask's set-bit count tells you the represented subset's size");
	return 0;
}

Count Set Bits

Set Bit Meaning

Loop Method

Brian Kernighan Method

Language Helpers

Practice

Chapter Quiz — Complete all 5 topics to unlock

Login to run this code