3

ビット カウントの実装は多数ありますが、私の場合は、任意の大きな数に最大で 2 つのセット ビットが含まれているかどうかをテストする必要があります。

私は次の関数を作成しましたが、これは非常に高速に見えますが、C# 用にさらに最適化できるかどうかを知りたいと考えていました。この関数は、ループで数百万回呼び出されます。

public static byte [] BitCountLookupArray = new byte []
{
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

// The parameter [number] will NEVER be negative.
public static bool HasSetBitCountOfLessThenThree (System.Numerics.BigInteger number)
{
    int sum = 0;
    byte [] bytes = null;

    bytes = number.ToByteArray();

    for (int i=0; i < bytes.Length; i++)
    {
        sum += BitCountLookupArray [bytes [i]];
    }

    return (sum < 3);
}

重要: 関数に送信される引数 [数値]が負になることは決してありません。

私が考えたいくつかのポイントは次のとおりです。

  • 関数を静的にする。終わり。
  • 静的ルックアップ配列の使用。終わり。
  • バイト数が 100,000 を超えることが多いため、配列インデックスの代わりにポインターを使用します。これがどれほど役立つかはわかりません。
  • 悲しいことに、.NET では保証できないインライン関数を強制します。

他の提案を受け入れます。

4

3 に答える 3

5

このようにして、さらに最適化できます

for (int i=0; i < bytes.Length; i++)
{
    sum += BitCountLookupArray [bytes [i]];
    if(sum >= 3)
    {
         return false   // This will stop the execution of unnecessary lines  
                        // as we need to know whether sum is less than 3 or not.                         
    }
}

return true;
于 2012-08-07T13:05:22.577 に答える
3

設定されているビットが 3 つ未満かどうかを知るだけでよいので、次のことをお勧めします。

// remove two bits
number &= number - 1;
number &= number - 1;
// if number != 0, then there were 3 or more bits set
return number.IsZero;

もちろん、Rain の方法も機能します。どの戦略がより高速になるかはわかりません。

別：

//remove one bit
number &= number - 1;
// if the number of bits left is 0 or 1, there were < 3 bits set
return number.IsZero || number.IsPowerOfTwo;

最初にテストして、後でビットを削除する方がおそらく高速です。

return number.IsZero ||        // zero bits?
    number.IsPowerOfTwo ||     // one bit?
    (number & (number - 1)).IsPowerOfTwo;  // two bits?
于 2012-08-07T15:50:01.250 に答える
1

sum == 3最も明らかな最適化は、その時点を過ぎた後の一致は重要ではないため、すぐにループから脱落することです。

bytes2 回設定する必要もありません。を使用するだけですbyte [] bytes = number.ToByteArray();が、ここでの利点はごくわずかです。

于 2012-08-07T13:05:49.007 に答える