算法的改进:在字节数组中计数设置位

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 ms,这太多了!

Answer 1

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

如果它总是你感兴趣的整个数组的计数,你可以将数组包装在一个类中,只要数组发生变化,该数组就会将计数存储在一个单独的整数中.(编辑:或者,确实,如评论中所述,使用java.util.BitSet.)