java - 算法改进 : Counting set bits in Byte-Arrays

Question

我们将知识以位的形式存储在字节数组中。计算设置位的数量非常慢。欢迎提出任何改进算法的建议:

public static int countSetBits(byte[] array) {
    int setBits = 0;

    if (array != null) {
        for (int byteIndex = 0; byteIndex < array.length; byteIndex++) {
            for (int bitIndex = 0; bitIndex < 7; bitIndex++) {
                if (getBit(bitIndex, array[byteIndex])) {
                    setBits++;
                }
            }
        }
    }
    return setBits;
}

public static boolean getBit(int index, final byte b) {
    byte t = setBit(index, (byte) 0);
    return (b & t) > 0;
}

public static byte setBit(int index, final byte b) {
    return (byte) ((1 << index) | b);
}

计算长度为 156'564 的字节数组的位数需要 300 毫秒，这太多了!

Answer 1

尝试Integer.bitcount来获取每个字节中设置的位数。如果可以从 byte 数组切换到 int 数组，效率会更高。如果这是不可能的，您还可以为所有 256 个字节构建一个查找表来快速查找计数，而不是迭代各个位。

如果您感兴趣的始终是整个数组的计数，则可以将数组包装在一个类中，每当数组更改时，该类将计数存储在单独的整数中。 (编辑:或者，实际上，正如评论中所述，使用 java.util.BitSet。)