[解決済み] 整数の1ビットが連続した領域にあるかどうかを、エレガントかつ高速にテストする方法はありますか？

質問

ビット値1の位置（32ビット整数の0から31まで）が連続した領域を形成しているかどうかをテストしたいのです。たとえば

00111111000000000000000000000000      is contiguous
00111111000000000000000011000000      is not contiguous

このテスト、つまりある関数が欲しいのです has_contiguous_one_bits(int) を移植できるようにしたい。

1つの明白な方法は、ポジションをループして最初のセットビットを見つけ、次に最初の非セットビットを見つけ、さらにセットビットがあるかどうかをチェックすることです。

より速い方法が存在するかどうか疑問に思っています。もし、最高と最低のセットビットを見つけるための高速な方法があるのなら、(ただし この質問 を見る限り、移植可能なものはないようです)、可能な実装は次のようになります。

bool has_contiguous_one_bits(int val)
{
    auto h = highest_set_bit(val);
    auto l = lowest_set_bit(val);
    return val == (((1 << (h-l+1))-1)<<l);
}

面白半分に、ビットが連続する最初の100個の整数を紹介します。

0 1 2 3 4 6 7 8 12 14 15 16 24 28 30 31 32 48 56 60 62 63 64 96 112 120 124 126 127 128 192 224 240 248 252 254 255 256 384 448 480 496 504 508 510 511 512 768 896 960 992 1008 1016 1020 1022 1023 1024 1536 1792 1920 1984 2016 2032 2040 2044 2046 2047 2048 3072 3584 3840 3968 4032 4064 4080 4088 4092 4094 4095 4096 6144 7168 7680 7936 8064 8128 8160 8176 8184 8188 8190 8191 8192 12288 14336 15360 15872 16128 16256 16320

は、（もちろん）次のような形式です。 (1<<m)*(1<<n-1) で、非負の m と n .

どのように解決するのですか？

解決方法

static _Bool IsCompact(unsigned x)
{
    return (x & x + (x & -x)) == 0;
}

簡単に説明します。

x & -x で設定されている最下位のビットを与えます。 x に設定されている最下位のビットを返します (または、もし x がゼロの場合はゼロ)。

x + (x & -x) は、連続した1の最下位の文字列を、より上位の単一の1に変換します（または、ゼロにラップします）。

x & x + (x & -x) はこれらの1ビットをクリアします。

(x & x + (x & -x)) == 0 は、他の 1 ビットが残っているかどうかをテストします。

長くなりました。

-x イコール ~x+1 は int は2の補数を想定していますが unsigned が望ましい)。でビットを反転させた後 ~x の下位1ビットを反転させるように1キャリーを追加します。 ~x の下位1ビットと最初の0ビットを反転させますが、その後停止します。このように -x の下位ビットと同じで、最初の1までが x の下位ビットと同じですが、上位ビットはすべて反転されます。(例 ~10011100 は 01100011 となり、1を足すと 01100100 となるので、低い方の 100 は同じですが、高い方の 10011 は反転して 01100 .) すると x & -x は両方で 1 になる唯一のビット、つまりその最下位 1 ビットを与えます ( 00000100 ). (もし x がゼロの場合 x & -x はゼロです)。

これを追加して x に追加すると、すべての連続した 1 を通してキャリーし、それらを 0 に変更します。 これは、次の上位の 0 ビットに 1 を残します (または、上位をキャリーして、ラップされた合計 0 を残します) ( 10100000 .)

と AND した場合 x とANDすると、1が0に変わったところ（キャリーで0が1に変わったところ）には0があります。つまり、上位にもう1ビットある場合のみ、結果が0にならないのです。