2

2 つの位置の間のビット文字列でポップ カウントを見つけるソリューションを探しています。

popcnt( 10(0101), 0, 3) = 1
popcnt( 100101(), 0, 0) = 0
popcnt( 10010(1), 0, 1) = 0

**私はオープンレンジを想定しており、右から左の順序を想定しています

標準のビット演算子とおそらく popcnt または同等のものを使用します。

違いがある場合は、2 つの文字列の違いの間の popcnt を探しています。文字列がbあり、2 つの位置でビットを交換するとします。たとえば、変更されたビット間0101110 -> 1101100 => 3に popcnt が必要です。2 つの間のビットが 3 である場合、 popcnt は 30101110 -> 110110010110

ビットハックでこれを行うための独創的な方法を見つけましたか?

4

1 に答える 1

7

最初に値をマスクして、関連するビットのみを取得します。

relevant = (value >> startBit) & ((1 << numOfBits) - 1);

編集：

上記は、未定義の動作を呼び出す場合numOfBits == 32(より正確には、場合numOfBits == CHAR_BIT * sizeof(int))。これを修正するには、その場合の特別な処理が必要です ( set relevant = value)。

次に、この質問で提案されている方法の 1 つを使用して、これらのビットの母数を見つけます。

答えを要約するには、GCC などのプラットフォーム固有の関数を使用できます__builtin_popcount。または、移植可能なソリューションが必要な場合は、Matt Howells の答えのような並列プレフィックス アルゴリズムを使用できます。

int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
于 2012-12-05T17:50:17.530 に答える