0

我们将知识作为位存储在字节数组中。计算设置位的数量非常慢。欢迎任何改进算法的建议：

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 毫秒，这太多了！

4

5 回答 5

5

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

如果它始终是您感兴趣的整个数组的计数，您可以将数组包装在一个类中，该类在数组更改时将计数存储在一个单独的整数中。（编辑：或者，确实，如评论中所述，使用java.util.BitSet。）

于 2013-02-15T12:19:04.877 回答
2

我将使用相同的全局循环，但不是在每个字节内循环，而是简单地使用大小为 256 的（预先计算的）数组将字节映射到它们的位数。那可能会非常有效。

如果您需要更高的速度，那么您应该单独维护计数并在设置位时增加计数并减少计数（但这意味着这些操作的额外负担很大，所以我不确定它是否适用于您）。

另一种解决方案将基于BitSet 实现：它使用一个长数组（而不是字节），这是它的计数方式：

658        int sum = 0;
659        for (int i = 0; i < wordsInUse; i++)
660            sum += Long.bitCount(words[i]);
661        return sum;
于 2013-02-15T12:22:39.913 回答
1

我会使用：

    byte[] yourByteArray = ...
    BitSet bitset = BitSet.valueOf(yourByteArray);  // java.util.BitSet
    int setBits = bitset.cardinality();

我不知道它是否更快，但我认为它会比你拥有的更快。让我知道？

你的方法看起来像

 public static int countSetBits(byte[] array) {
     return BitSet.valueOf(array).cardinality();
 }

你说：

我们将知识作为位存储在字节数组中。

我建议使用 a BitSet。它为您提供了方便的方法，而且您似乎对位感兴趣，而不是字节，因此与byte[]. （在内部它使用 a long[]）。

于 2013-02-15T12:25:38.400 回答
0

到目前为止，最快的方法是计算位集，在“并行”中，方法称为汉明权重Integer.bitCount(int i)，据我所知 是在实现的。

于 2016-12-06T11:36:41.937 回答
-1

据我了解，

1 字节 = 8 位

因此，如果 Byte Array size = n ，那么总位数不是 = n*8 吗？

如果我的理解有误，请纠正我

谢谢维诺德

于 2013-02-15T13:12:22.913 回答