Skip to content

Instantly share code, notes, and snippets.

@isaacl
Last active May 9, 2017 13:56
Show Gist options
  • Save isaacl/338a3f88e7d18a0c64bf9aed6e4a816b to your computer and use it in GitHub Desktop.
Save isaacl/338a3f88e7d18a0c64bf9aed6e4a816b to your computer and use it in GitHub Desktop.
BitCount
class BitCountRunner {
static final int MAX_INT = 1 << 14;
static final long MAX_LONG = 1 << 14;
int intIntrinsic() {
int cnt = 0;
for (int i = 0; i < MAX_INT; i++)
cnt += Integer.bitCount(i);
return cnt;
}
int intJDK() {
int cnt = 0;
for (int i = 0; i < MAX_INT; i++)
cnt += BitCounts.bitCountInt(i);
return cnt;
}
int intNew() {
int cnt = 0;
for (int i = 0; i < MAX_INT; i++)
cnt += BitCounts.bitCountIntNew(i);
return cnt;
}
int longIntrinsic() {
int cnt = 0;
for (long i = 0; i < MAX_LONG; i++)
cnt += Long.bitCount(i);
return cnt;
}
int longJDK() {
int cnt = 0;
for (long i = 0; i < MAX_LONG; i++)
cnt += BitCounts.bitCountLong(i);
return cnt;
}
int longNew() {
int cnt = 0;
for (long i = 0; i < MAX_LONG; i++)
cnt += BitCounts.bitCountLongNew(i);
return cnt;
}
}
public class BitCounts {
public static final int bitCountLong(long i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x5555555555555555L);
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
}
public static final int bitCountLongNew(long i)
{
i -= (i >>> 1) & 0x5555555555555555L;
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
return (int)((i * 0x0101010101010101L) >>> 56);
}
public static final int bitCountInt(int i) {
// HD, Figure 5-2
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
public static final int bitCountIntNew(int i) {
i -= (i >>> 1) & 0x55555555;
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
return (i * 0x01010101) >>> 24;
}
}
package org.openjdk.jmh.samples
import org.openjdk.jmh.annotations._
import java.util.concurrent.TimeUnit
import org.BitCounts
@State(Scope.Thread)
@BenchmarkMode(Array(Mode.AverageTime))
@OutputTimeUnit(TimeUnit.NANOSECONDS)
class BitCountTest {
@Benchmark
def bitCountInt = {
var i = 0
var cnt = 0
val max = 1 << 14
while (i < max) {
cnt += BitCounts.bitCountInt(i)
i += 1
}
cnt
}
@Benchmark
def bitCountIntNew = {
var i = 0
var cnt = 0
val max = 1 << 14
while (i < max) {
cnt += BitCounts.bitCountIntNew(i)
i += 1
}
cnt
}
@Benchmark
def bitCountLong = {
var i = 0l
var cnt = 0
val max = 1l << 14
while (i < max) {
cnt += BitCounts.bitCountLong(i)
i += 1l
}
cnt
}
@Benchmark
def bitCountLongNew = {
var i = 0l
var cnt = 0
val max = 1l << 14
while (i < max) {
cnt += BitCounts.bitCountLongNew(i)
i += 1l
}
cnt
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment