WikiGalaxy
Counting Set Bits
Introduction:
Counting set bits in a binary number is a common operation in computer science, often used in algorithms and data analysis. A set bit is a bit with a value of 1.
Example 1: Simple Iteration
Simple Iteration Method:
This method involves iterating through each bit of the number and counting the number of 1s.
public class CountSetBits {
public static void main(String[] args) {
int num = 29; // Binary: 11101
int count = 0;
while (num > 0) {
count += num & 1;
num >>= 1;
}
System.out.println("Set Bits: " + count);
}
}
Explanation:
The program iterates through each bit of the number 29 (binary 11101) and counts the number of set bits, resulting in a count of 4.
Example 2: Brian Kernighan's Algorithm
Brian Kernighan's Algorithm:
This algorithm is an efficient way to count set bits by turning off the rightmost set bit one at a time.
public class CountSetBits {
public static void main(String[] args) {
int num = 29; // Binary: 11101
int count = 0;
while (num > 0) {
num &= (num - 1);
count++;
}
System.out.println("Set Bits: " + count);
}
}
Explanation:
In each iteration, the algorithm turns off the rightmost set bit of the number, effectively reducing the number of set bits by one until the number becomes zero.
Example 3: Using Java's Built-in Method
Java's Built-in Method:
Java provides a built-in method to count set bits using Integer.bitCount().
public class CountSetBits {
public static void main(String[] args) {
int num = 29; // Binary: 11101
int count = Integer.bitCount(num);
System.out.println("Set Bits: " + count);
}
}
Explanation:
The Integer.bitCount() method is a convenient and efficient way to count the number of set bits in an integer.
Example 4: Lookup Table Method
Lookup Table Method:
This method uses a precomputed table to quickly find the number of set bits for a small range of integers.
public class CountSetBits {
private static final int[] BIT_COUNT = new int[256];
static {
for (int i = 0; i < 256; i++) {
BIT_COUNT[i] = (i & 1) + BIT_COUNT[i / 2];
}
}
public static void main(String[] args) {
int num = 29; // Binary: 11101
int count = BIT_COUNT[num & 0xff] + BIT_COUNT[(num >> 8) & 0xff] +
BIT_COUNT[(num >> 16) & 0xff] + BIT_COUNT[(num >> 24) & 0xff];
System.out.println("Set Bits: " + count);
}
}
Explanation:
The lookup table stores the number of set bits for all numbers from 0 to 255, allowing for fast retrieval and summation of set bits in larger integers.
Example 5: Recursive Method
Recursive Method:
A recursive approach to count set bits by breaking down the problem into smaller subproblems.
public class CountSetBits {
public static void main(String[] args) {
int num = 29; // Binary: 11101
int count = countSetBits(num);
System.out.println("Set Bits: " + count);
}
private static int countSetBits(int num) {
if (num == 0) return 0;
return (num & 1) + countSetBits(num >> 1);
}
}
Explanation:
The recursive method checks the least significant bit and then calls itself with the number right-shifted by one position, continuing until the number is zero.
