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 実装に基づいています。これは long (バイトではなく) の配列を使用し、カウント方法は次のとおりです。

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 に答える
-1

私の理解によると、

1バイト=8ビット

したがって、バイト配列のサイズ= nの場合、ビットの総数= n * 8ではありませんか?

私の理解が間違っている場合は私を訂正してください

ありがとうVinod

于 2013-02-15T13:12:22.913 に答える