Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Count bits
import java.util.Date;
public class Count {
static int[] _counts = {
0,1,1,2,
1,2,2,3,
1,2,2,3,
2,3,3,1
};
static int[] counts;
private static void init() {
counts = new int[(1 << 16)];
for (int i = 0; i <= 0xFFFF; i++) { // Need unsigned shorts!
counts[i] = _counts[(i & 0xF)] +
_counts[((i >> 4) & 0xF)] +
_counts[((i >> 8) & 0xF)] +
_counts[((i >> 12) & 0xF)];
}
}
public static int countBits(int x) {
if (counts == null) init();
int t;
for (t = 0; x != 0; x >>>= 16) t += counts[(x & 0xFFFF)];
return t;
}
public static int countBitsNaive(int x) {
int t;
for (t = 0; x != 0; x >>>= 1) t += (x & 1);
return t;
}
public static int countBitsK(int x) {
int t;
for (t = 0; x != 0; t++) x &= x - 1;
return t;
}
public static void main(String[] args) {
// init();
int min = 0 - (1 << 24);
int max = 1 << 24;
Date a; Date b;
a = new Date();
for (int i = min; i <= max; i++) countBitsNaive(i);
b = new Date();
System.out.println("Naïve: " + (b.getTime() - a.getTime()));
a = new Date();
for (int i = min ; i <= max; i++) countBits(i);
b = new Date();
System.out.println("Table: " + (b.getTime() - a.getTime()));
a = new Date();
for (int i = min ; i <= max; i++) countBitsK(i);
b = new Date();
System.out.println("Kernighan: " + (b.getTime() - a.getTime()));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment