这是我目前正在使用的工具。当前,Mark Peters的答案通常是最快的,但使用-server
标志的话,Carl的更快。另外,mikera在服务器模式下表现得更具有竞争力(虽然仍然比Carl/Mark的慢)。
import java.util.Random;
public abstract class Harness {
public static void main(String[] args) {
while (true) {
long[] randomData = new long[4096];
Random r = new Random();
for (int i = 0; i < randomData.length; i++) {
randomData[i] = r.nextLong();
}
long[] buffer = new long[64];
Harness[] versions = new Harness[] {
new Control(randomData, buffer),
new Carl(randomData, buffer),
new MarkPeters(randomData, buffer),
new MarkPetersServer64Bit(randomData, buffer),
new Rsp2(randomData, buffer),
new Mikera(randomData, buffer)
};
for (Harness v : versions) {
v.doTest();
}
}
}
private final long[] buffer;
private final long[] randomData;
protected Harness(long[] randomData, long[] buffer) {
this.randomData = randomData;
this.buffer = buffer;
}
public void doTest() {
long start = System.nanoTime();
long count = 0;
for (int times = 0; times < 1000; times++) {
for (int i = 0; i < randomData.length; i++) {
count = decompose(buffer, randomData[i]);
}
}
long end = System.nanoTime();
long l = 0;
for ( int i = 0; i < count; i++ ) {
l |= buffer[i];
}
System.out.println(getClass().getSimpleName() + " took " + (end - start)
/ 1000000.0 + " ms - last base: " + l);
}
protected abstract int decompose(long[] buffer, long base);
private static class Control extends Harness {
protected Control(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
return 0;
}
}
private static class Carl extends Harness {
protected Carl(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
final int count = Long.bitCount(base);
for (int i = 0; i < count; i++) {
base ^= (buffer[i] = Long.lowestOneBit(base));
}
return count;
}
}
private static class Mikera extends Harness {
protected Mikera(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
while (base != 0) {
long mask = base & (-base);
base &= ~mask;
buffer[count++] = mask;
}
return count;
}
}
private static class Rsp1 extends Harness {
protected Rsp1(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
if (0 != (base & 1)) {
buffer[count++] = 1;
}
base >>>= 1;
for (long bit = 1; 0 < bit && bit <= base; ) {
if (0 < (base & bit)) {
buffer[count++] = (bit <<= 1);
}
}
return count;
}
}
private static class Rsp2 extends Harness {
protected Rsp2(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
for (long bit = 1; 0 != base; bit <<= 1, base >>>= 1) {
if (0 < (base & 1)) {
buffer[count++] = bit;
}
}
return count;
}
}
private static class MarkPeters extends Harness {
protected MarkPeters(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = Long.bitCount(base);
for (int i = 0; i < count; i++) {
base -= (buffer[i] = Long.lowestOneBit(base));
}
return count;
}
}
private static class MarkPetersServer64Bit extends Harness {
protected MarkPetersServer64Bit(long[] randomData, long[] buffer) {
super(randomData, buffer);
}
@Override
protected int decompose(long[] buffer, long base) {
int count = 0;
while ( 0 != (base ^= (buffer[count++] = Long.lowestOneBit(base))));
return count;
}
}
}
样例输出
哪种方法最好取决于情况。
非服务器,32位JVM
Control took 41.175272 ms - last base: 0
Carl took 691.966919 ms - last base: 5852835112840111303
MarkPeters took 642.230253 ms - last base: 5852835112840111303
MarkPetersServer64Bit took 742.594626 ms - last base: 5852835112840111303
Rsp2 took 3886.203787 ms - last base: 5852835112840111303
Mikera took 1044.451494 ms - last base: 5852835112840111303
获胜者:MarkPeters
服务器,32位JVM
Control took 2.354383 ms - last base: 0
Carl took 508.687401 ms - last base: 338317437500027646
MarkPeters took 521.831297 ms - last base: 338317437500027646
MarkPetersServer64Bit took 727.052206 ms - last base: 338317437500027646
Rsp2 took 3811.75662 ms - last base: 338317437500027646
Mikera took 665.252599 ms - last base: 338317437500027646
获胜者: 卡尔
服务器(隐式或显式),64位JVM
Control took 0.007186 ms - last base: 0
Carl took 543.701859 ms - last base: -8898262206218882664
MarkPeters took 439.706079 ms - last base: -8898262206218882664
MarkPetersServer64Bit took 391.831055 ms - last base: -8898262206218882664
Rsp2 took 1861.40449 ms - last base: -8898262206218882664
Mikera took 435.964319 ms - last base: -8898262206218882664
胜者: MarkPetersServer64Bit
注意:据我所知,目前没有可在非服务器模式下运行的可比较的64位JVM。请参见这里:
64位Java中是否同时支持-client和-server VM模式?
目前只有Java HotSpot Server VM支持64位操作,并且使用-d64时,-server选项是隐含的。这可能会在将来的版本中更改。
BitTwiddling
是静态实用程序类,具有分解方法。 - CarlcompareIterations = Integer.MAX_VALUE >> 2
。 - Carl