长整型的快速位运算

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

我的问题是：有没有更快的方法来做这件事？

- Amir Afghani

---

我希望这个数字不是负数... - nicomp

我并不认为数字为负数会引起问题。例如：-8646761407372591104L。它返回的结果是[37, 39, 44, 48, 60, 64]，这是正确的。你能给出一个反例吗？ - Amir Afghani

这个方法应该可以正常工作，不受符号影响，因为 >>> 是逻辑移位，它会在另一端插入零，并最终用零填充每个位，而不是算术移位。 - Chai T. Rex

根据需要，如果不用建立列表，你能更快地进行操作。列表只是信息的转换，因此你可以将测试逻辑和实际索引处理合并，消除装箱和列表的需求。 - Durandal

Answer 1

最快的方法

BitBank对这个问题的回答比本回答下面的两种方法快大约两倍。它借鉴了BitBank的答案，并通过使用位操作来重复关闭最低有效位，而不是将一位右移并跟踪移位量，在我的机器上使其比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答案的改进

• 不需要跟踪我们跳过了多少位。
• 快速将最后一个1位变为0位。
• 双重转换为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;
}

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

改进

• 使用Long.bitCount(n)预先计算所需容量（使用处理器的非常快速的“popcount”指令）可以加快方法的速度。您可以通过使用new ArrayList<>(Long.bitCount(n))来更改此设置。
• 使用ArrayList<Integer>比使用byte[]慢，因为：
  • 必须浪费时间查找低值（-127到128）的Integer值从Integer缓存放入ArrayList中。
  • 使用存储在结果List<Integer>中的int时，必须浪费时间，因为您必须从List<Integer>检索Integer，然后检索int。
• byte[]使用大约1/4（32位系统）或1/8（64位系统）的ArrayList<Integer>内存，因为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;
}

您也可以将其更改为从零开始计算位位置，而不是从一开始计算。

改进

• 避免需要反复对数字执行>>>。
• 避免需要反复对位位置执行++。
• 避免需要检查数字是否已达到零。
• 避免了一些分支预测错误。

- Chai T. Rex

---

谢谢！解释得非常好。 - Amir Afghani

byte[] 更可取，因为它将内存压缩到 int[] 的约 1/4。此外，Java 将自动将 byte 转换为 int，因此您可以执行像 int a = result[5]; 或 result[5] * 500 这样的操作，并获得与 result[5] 一直是 int 一样的结果（乘以 500 不会溢出，因为所有内容都被视为 int），并且事情将像数组是 int 一样工作。基本上，您可以免费获得更少的内存使用。 - Chai T. Rex

你怎么知道它更快？你有测量过吗，还是这只是一个逻辑上的结论？避免分支会很好，但我不确定该如何做到... - assylias

@assylias 所谓“缺失的分支”，是指for循环的条件(n != 0L)不再需要进行检查，因为在更丑陋的版本中已经省略了该for循环。至于测量，我使用了java.util.Random提供的输入，在每个版本上都进行了100万次不规范的测量，并使用了time java ClassName。更丑陋的版本多次以约0.35秒的速度运行，不太丑陋的版本多次以约0.38秒的速度运行，而问题中的代码多次以约0.60秒的速度运行。 - Chai T. Rex

我最初建议使用展开循环的方法，但因为它需要进行完整的64次比较，而原始循环在识别到最高有效位后就停止了，这可能会在不到64位的情况下发生。更好的方法是反转比较顺序，从第64位开始，然后将前32位放入if块中检查数字是否大于2^32。在该if块的末尾，从源数字中删除前32位。然后重复下一个16位、8位和最后8位。 - Paul Ostrowski

Answer 2

如果您不介意使用内部函数，您可以拥有一个更快的版本。Long.numberOfTrailingZeros()将使用CPU内部函数计算从最低有效位开始的连续零比特数（在x86处理器上使用BSF指令）。

对于稀疏值，这将比所有其他循环方法更快，因为它在主循环中没有任何条件或分支，跳过任意数量的0的运行只需要一次迭代，并且对于64位long，BSF内部函数在Intel Haswell CPU上只有3个时钟周期的延迟。

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

    byte bitPosition = 0;
    for (int i = 0; n != 0L; i++) {
        final byte bitsToSkip = (byte) (Long.numberOfTrailingZeros(n) + 1);
        n >>>= bitsToSkip;
        bitPosition += bitsToSkip;
        result[i] = bitPosition;
    }

    return result;
}

- BitBank

---

谢谢您的回答。您能解释一下为什么这个方法比其他针对'稀疏'值的解决方案更快吗？再次感谢，我认为这是一种可读性高的方法，我也不介意使用JDK API。 - Amir Afghani

@AmirAfghani，一般情况下，这种方法比我的两种方法快两倍（或者比问题中的方法快四倍）。我建议使用这种方法。 - Chai T. Rex

谢谢@ChaiT.Rex - 这种方法还需要稍微整理一下。它目前不能编译为Java，并且签名与你的方法不符合API的要求。你测试过这个方法是否返回一个byte[]吗？很想看到你在答案中包含结果。 - Amir Afghani

感谢您的编辑，@Chai。我已在C中进行了测试，不再拥有可用的Java环境，因此我相信您的新版本将按照OP的意图执行。主要目的是尽可能利用内置函数/SIMD。 - BitBank

@BitBank 我测试了问题方法的结果与这个版本一百万个随机long的结果相匹配。您使用内置函数的想法非常好，因为在过去几分钟内，在我的机器上进行了一百万次迭代，它始终给出以下结果：全部使用内置函数：0.18秒，我的循环展开：0.35秒，问题中的方法：0.69秒。 - Chai T. Rex

Answer 3

在这里，我使用了一种简单的方法，亚线性时间。您可以决定是从左边还是右边计数，在printf("%ld\n", 32-pos)中，您可以考虑32-pos或pos。

bit_pos(unsigned long x)
{
    unsigned long pos;
    unsigned long w;
    while(x) {
        /* extract the rightmost `1` in `w` then remove it */
        w = x&-x;
        x-=w;

        if (w) {
            /* compute number of trailing zeros (location of 1) for w */
            pos = 1;
            if (!(w >> 16)) {pos+=16;w<<=16;}
            if (!(w >> 24)) {pos+= 8;w<<= 8;}
            if (!(w >> 28)) {pos+= 4;w<<= 4;}
            if (!(w >> 30)) {pos+= 2;w<<= 2;}
            pos = pos - (w >> 31);
            printf("%ld\n", 32-pos);
        }
    }
    printf("\n");
}

main()
{
    bit_pos(2UL+4+32+1024);
    bit_pos(3456789UL);
}

- alinsoar