Brian Kernighan's Algorithm
นับจำนวน bit 1 ใน binary representation ของ integer
หลักการ: n & (n-1) ลบ bit 1 ตัวท้ายสุดออก ทำซ้ำจน n=0 จำนวนรอบ = จำนวน set bits
ตัวอย่างโค้ด
public class Demo {
// Brian Kernighan's Algorithm
static int countSetBits(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // clear least significant set bit
count++;
}
return count;
}
// Built-in (Java 5+)
static int countSetBitsBuiltin(int n) {
return Integer.bitCount(n);
}
// Long version
static int countSetBitsLong(long n) {
return Long.bitCount(n);
}
public static void main(String[] args) {
int n = 11; // binary: 1011
System.out.println("Number: " + n + " (binary: " + Integer.toBinaryString(n) + ")");
System.out.println("Brian Kernighan: " + countSetBits(n));
System.out.println("Integer.bitCount: " + countSetBitsBuiltin(n));
// Test multiple values
for (int test : new int[]{0, 1, 7, 15, 16, 31, 32, 1023, 1024}) {
System.out.printf("%5d (0x%04X) → %d bits%n", test, test, countSetBits(test));
}
}
}
ผลลัพธ์
Number: 11 (binary: 1011)
Brian Kernighan: 3
Integer.bitCount: 3
0 (0x0000) → 0 bits
1 (0x0001) → 1 bits
7 (0x0007) → 3 bits
15 (0x000F) → 4 bits
16 (0x0010) → 1 bits
31 (0x001F) → 5 bits
32 (0x0020) → 1 bits
1023 (0x03FF) → 10 bits
1024 (0x0400) → 1 bits
Complexity
- Brian Kernighan: O(k) where k = number of set bits (ดีกว่า O(log n) ของ shift loop)
- Integer.bitCount(): Hardware instruction (POPCNT) ถ้ารองรับ → O(1) เร็วที่สุด
Applications
- Hamming distance:
Integer.bitCount(x ^ y) - Parity bit, Error detection
- Bitset operations, Bloom filters
- Chess programming (bitboards)
