java - 在 Java 中有点旋转 - 将 long 分解为位掩码的 long[]

Question

我正在将一个 long 分解成一个 long[] 的单位 long，方法是

public static 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;
}

但我觉得可能有更快的方法来执行此操作，因为似乎有一些重复的步骤。例如，计算位数应该已经非常接近获得填充结果所需的所有信息。

有什么建议吗？我熟悉过早的优化口头禅，因此为什么我没有在我的时间进一步插入我的解决方案，但也许其他人之前已经看到过这个或者沉迷于优化......编辑:请通过 test harness Mark provided below 运行任何建议.令我感到非常惊讶的是，我的第一 react 竟然是正确的。

测试代码，在 JUnit 方法中:

Random rng = new Random();
long size = 0;
long[] hold = new long[Long.SIZE];
System.out.println("init:"+Long.toBinaryString(BitTwiddling.bitmask(rng.nextInt(Long.SIZE)))); //initialize BitTwiddling internals
long start = System.currentTimeMillis();
for (int i=0; i<compareIterations; i++) size+= BitTwiddling.decompose(hold,rng.nextInt(Integer.MAX_VALUE));
long delta = System.currentTimeMillis() - start;
double base = (double)size/delta;

size = 0;
start = System.currentTimeMillis();
for (int i=0; i<compareIterations; i++) size += BitTwiddling.decomposeAlt(hold, rng.nextInt(Integer.MAX_VALUE));
long delta2 = System.currentTimeMillis() - start;
double base2 = (double)size/delta2;

然后比较base和base2

Answer 1

好吧，在长期努力地击败您的原始代码之后，我找到了一个通过无耻地窃取您的代码并进行调整而始终击败您的代码(在我的环境中)的代码。

    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;
    }

唯一的区别:使用减法而不是异或。我不认为有任何边缘情况；我当然没有找到任何。不知道为什么它们没有针对同一事物进行优化(假设没有边缘情况)，但它确实使我的速度始终更快(同样，在我的机器上)。我已将此版本添加到测试答案中。

编辑 我想它不能被优化的原因是因为编译器不知道操作数总是小于基数(因为我们是从低位到高位) .

编辑 #2 设置了 -server 标志后，Carl 的速度始终比我的快一点。

编辑 #3 是的，当在 64 位 JVM 上运行时，速度要快得多:

    protected int decompose(long[] buffer, long base) {
        int count = 0;
        while ( 0 != (base -= (buffer[count++] = Long.lowestOneBit(base))));
        return count;
    }

(或等效的 xor 版本)，因为它可以使用 native 处理器操作执行 64 位比较。