java - 长的快速按位运算

Question

我知道我可以编写以下方法来计算 long 的设置位索引:

private static List<Integer> bitPositions(long number) {
    final List<Integer> positions = new ArrayList<>();
    int position = 1;
    while (number != 0) {
        if ((number & 1L) != 0) {
            positions.add(position);
        }
        position++;
        number = number >>> 1;
    }
    return positions;
}

我的问题是: 有没有更快的方法来做到这一点 ？

Answer 1

最快的方法

BitBank's answer to this question 的速度大约是这个答案下面的两种方法的两倍。这窃取了 BitBank 答案中的想法，并通过使用位旋转反复关闭最不重要的一位而不是右移一位，使其比我的机器上的速度快 73%(比问题的方法快 9 倍)离开右端并跟踪发生了多少变化。

private static final byte[] bitPositions(long n) {
    final byte[] result = new byte[Long.bitCount(n)];

    for (int i = 0; n != 0L; i++) {
        result[i] = (byte) ((byte) Long.numberOfTrailingZeros(n) + 1);
        n &= n - 1L;  // Change least-significant one bit to a zero bit.
    }

    return result;
}

BitBank 答案的改进

无需跟踪我们跳过了多少位。

快速将最后一位变为零位。

对 byte 的双重转换稍微加快了速度。我认为这是因为它允许 byte 大小而不是 int 大小的算术。

手动融合

正如 Durandal 在问题的评论中指出的那样，您可以交易以下内容:

for (int bitPosition : bitPositions(n)) {
    // Do something with `bitPosition`.
}

对于跳过方法调用并执行此操作的样式:

long temp = n;
while (temp != 0L) {
    int bitPosition = Long.numberOfTrailingZeros(temp) + 1;
    temp &= temp - 1L;  // Change least-significant one bit to a zero bit.

    // Do something with `bitPosition`.
}

融合的好处

无需浪费时间调用方法。

无需创建或垃圾收集数组，节省时间和内存。

在您使用它的整个过程中，位位置可能会保留在一个非常快的 CPU 寄存器中，而不是可能需要将它写入 RAM 中的数组(这要慢得多)，然后再从 RAM 中读取它。

融合的缺点

这比进行明确命名的方法调用和干净地使用结果数组要丑一些。

如果您的代码中有多个地方需要计算数字的位位置，则必须在每个地方重复代码(违反 DRY )。

如果您想对相同数字的位位置进行多次单独迭代，则必须重新计算位位置，而不是重用先前生成的数组。

但是，如果重新计算位位置比从 RAM 中的数组加载预先计算的位置更快，这可能不是实际的缺点。

最慢的方法

这是一种产生相同结果的方法(仅在 byte[] 而不是 List<Integer> 中)大约快两倍:

private static final byte[] bitPositions(long n) {
    final byte[] result = new byte[Long.bitCount(n)];

    int i = 0;
    for (byte bit = 1; n != 0L; bit++) {
        if ((n & 1L) != 0) result[i++] = bit;
        n >>>= 1;
    }

    return result;
}

我建议将 byte bit = 1 循环中的 for 更改为 byte bit = 0 以切换到从零而不是从一开始对位位置进行编号的传统方法。

改进

使用 Long.bitCount(n) 预先计算所需的容量(使用处理器的非常快速的“popcount”指令)可以大大加快您的方法。您可以通过使用 ArrayList 制作 new ArrayList<>(Long.bitCount(n)) 来更改此设置。

使用 ArrayList<Integer> 比 byte[] 慢，因为:

必须浪费时间从 the -127 cache 查找低值( 128 到 Integer )Integer 值以将它们放入 ArrayList 。

稍后使用存储在结果 int 中的 List<Integer> 时必须浪费时间，因为您必须从 Integer 检索 List<Integer> ，然后从 int 检索 Integer 。

byte[] 使用 ArrayList<Integer> 内存的大约 1/4(32 位系统)或 1/8(64 位系统)，因为 byte 比指向 Integer 的指针小得多。

比最慢的方法快一点，但更丑

正如另一个人已删除的答案所建议的那样，循环展开在我的机器上进一步加快了速度(检查您的机器上是否也是如此):

private static final byte[] bitPositions(final long n) {
    final byte[] result = new byte[Long.bitCount(n)];

    int i = 0;
    if ((n &                    1L) != 0L) result[i++] = 1;
    if ((n &                    2L) != 0L) result[i++] = 2;
    if ((n &                    4L) != 0L) result[i++] = 3;
    if ((n &                    8L) != 0L) result[i++] = 4;
    if ((n &                   16L) != 0L) result[i++] = 5;
    if ((n &                   32L) != 0L) result[i++] = 6;
    if ((n &                   64L) != 0L) result[i++] = 7;
    if ((n &                  128L) != 0L) result[i++] = 8;
    if ((n &                  256L) != 0L) result[i++] = 9;
    if ((n &                  512L) != 0L) result[i++] = 10;
    if ((n &                 1024L) != 0L) result[i++] = 11;
    if ((n &                 2048L) != 0L) result[i++] = 12;
    if ((n &                 4096L) != 0L) result[i++] = 13;
    if ((n &                 8192L) != 0L) result[i++] = 14;
    if ((n &                16384L) != 0L) result[i++] = 15;
    if ((n &                32768L) != 0L) result[i++] = 16;
    if ((n &                65536L) != 0L) result[i++] = 17;
    if ((n &               131072L) != 0L) result[i++] = 18;
    if ((n &               262144L) != 0L) result[i++] = 19;
    if ((n &               524288L) != 0L) result[i++] = 20;
    if ((n &              1048576L) != 0L) result[i++] = 21;
    if ((n &              2097152L) != 0L) result[i++] = 22;
    if ((n &              4194304L) != 0L) result[i++] = 23;
    if ((n &              8388608L) != 0L) result[i++] = 24;
    if ((n &             16777216L) != 0L) result[i++] = 25;
    if ((n &             33554432L) != 0L) result[i++] = 26;
    if ((n &             67108864L) != 0L) result[i++] = 27;
    if ((n &            134217728L) != 0L) result[i++] = 28;
    if ((n &            268435456L) != 0L) result[i++] = 29;
    if ((n &            536870912L) != 0L) result[i++] = 30;
    if ((n &           1073741824L) != 0L) result[i++] = 31;
    if ((n &           2147483648L) != 0L) result[i++] = 32;
    if ((n &           4294967296L) != 0L) result[i++] = 33;
    if ((n &           8589934592L) != 0L) result[i++] = 34;
    if ((n &          17179869184L) != 0L) result[i++] = 35;
    if ((n &          34359738368L) != 0L) result[i++] = 36;
    if ((n &          68719476736L) != 0L) result[i++] = 37;
    if ((n &         137438953472L) != 0L) result[i++] = 38;
    if ((n &         274877906944L) != 0L) result[i++] = 39;
    if ((n &         549755813888L) != 0L) result[i++] = 40;
    if ((n &        1099511627776L) != 0L) result[i++] = 41;
    if ((n &        2199023255552L) != 0L) result[i++] = 42;
    if ((n &        4398046511104L) != 0L) result[i++] = 43;
    if ((n &        8796093022208L) != 0L) result[i++] = 44;
    if ((n &       17592186044416L) != 0L) result[i++] = 45;
    if ((n &       35184372088832L) != 0L) result[i++] = 46;
    if ((n &       70368744177664L) != 0L) result[i++] = 47;
    if ((n &      140737488355328L) != 0L) result[i++] = 48;
    if ((n &      281474976710656L) != 0L) result[i++] = 49;
    if ((n &      562949953421312L) != 0L) result[i++] = 50;
    if ((n &     1125899906842624L) != 0L) result[i++] = 51;
    if ((n &     2251799813685248L) != 0L) result[i++] = 52;
    if ((n &     4503599627370496L) != 0L) result[i++] = 53;
    if ((n &     9007199254740992L) != 0L) result[i++] = 54;
    if ((n &    18014398509481984L) != 0L) result[i++] = 55;
    if ((n &    36028797018963968L) != 0L) result[i++] = 56;
    if ((n &    72057594037927936L) != 0L) result[i++] = 57;
    if ((n &   144115188075855872L) != 0L) result[i++] = 58;
    if ((n &   288230376151711744L) != 0L) result[i++] = 59;
    if ((n &   576460752303423488L) != 0L) result[i++] = 60;
    if ((n &  1152921504606846976L) != 0L) result[i++] = 61;
    if ((n &  2305843009213693952L) != 0L) result[i++] = 62;
    if ((n &  4611686018427387904L) != 0L) result[i++] = 63;
    if ((n & -9223372036854775808L) != 0L) result[i++] = 64;

    return result;
}

您还可以更改此设置以从零而不是一开始计算位位置。

改进

避免对号码重复执行 >>> 的需要。

避免需要在位位置上重复执行 ++。

避免需要检查数字是否已达到零。

避免一些分支错误预测。