9

新しい候補者に面接するときは、通常、特定のバイト変数の値が1のビット数をカウントするCコードを作成するように依頼します（たとえば、バイト3には2つの1ビットがあります）。私は、8回の右シフトや、256個の事前計算された結果の定数テーブルのインデックス付けなどの一般的な答えをすべて知っています。

しかし、事前に計算されたテーブルを使用せずに、よりスマートな方法はありますか？1ビット数を計算するバイト演算（AND、OR、XOR、+、-、バイナリ否定、左右シフト）の最短の組み合わせは何ですか？

4

3 に答える 3

4

パフォーマンス特性が異なる、より高速なソリューションが少なくとも2つあります。

  1. 1を引き、新しい値と古い値をANDします。ゼロになるまで繰り返します。反復回数を数えます。複雑さ：O（B）、ここでBは1ビットの数です。

    int bits(unsigned n)
{
    for (int i = 0; n; ++i)
    {
        n &= n - 1;
    }
    return i;
}

  2. ワードサイズに達するまで、ビットのペアを追加し、次に4つのグループ、次に8つのグループを追加します。1回のパスで各レベルのすべてのグループを追加できるトリックがあります。複雑さ：O（log（N））、ここでNはビットの総数です。

    int bits(uint32 n)
{
    n = (n & 0x55555555) + ((n >>  1) & 0x55555555);
    n = (n & 0x33333333) + ((n >>  2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >>  4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >>  8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + (n >> 16);
    return n;
}

    このバージョンは少しナイーブです。少し考えれば、いくつかの操作を避けることができます。

于 2010-05-24T11:00:55.210 に答える
3

これがビットをいじるハックの方法のリストです

于 2010-05-24T11:03:14.047 に答える
0

Javaはこの方法でそれを行います（32ビット整数を使用）（14回の計算）

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

16ビット整数（短い）の場合、メソッドは次のように書き直すことができます。

private static int bitCount(int i) {
   // HD, Figure 5-2
   i = i - ((i >>> 1) & 0x5555);
   i = (i & 0x3333) + ((i >>> 2) & 0x3333);
   i = (i + (i >>> 4)) & 0x0f0f;
   i = i + (i >>> 4);
   i = i + (i >>> 8);
   return i & 0x3f;
}

8ビット整数（バイト）の場合、少し複雑ですが、一般的な考え方はそこにあります。

高速ビットカウント機能の詳細については、次のリンクを確認してください：http: //gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

任意の整数の最速/最も簡単な方法。最良の場合はO（0）、最悪の場合はO（n）（nは値のビット数）です。

static private int bitcount(int n)  {
   int count = 0 ;
   while (n != 0)  {
      count++ ;
      n &= (n - 1) ;
   }
   return count ;
}
于 2010-05-24T11:13:02.260 に答える