これがあなたが望むことをするコードです:
unsigned chk_bits(unsigned int x) {
unsigned i;
if (x != 0 && (x & (x-1)) != 0) {
/* More than one '1' bit */
for (i = ~(~0U >> 1); (x & i) == 0; i >>= 1)
; /* Intentionally left blank */
return x & ~i;
}
return x;
}
符号なしの数値を扱っていると仮定していることに注意してください。符号拡張により、符号付き整数で右シフトが定義されているため、これは通常より安全です。
このif
ステートメントは、 に複数のビットが設定されているかどうかをチェックしx
ます。は、最初の '1' の最下位ビットをオフにした場合x & (x-1)
と同じ数を取得する既知の方法です(たとえば、 isの場合、is です。したがって、 は次のように言います:x
x
101100100
x & (x-1)
101100000
if
x がゼロではなく、1 に設定された最初のビット (LSB から MSB の順) をオフにすると、0 以外の値になる場合は...
これは、 に複数のビットが設定されていると言うのと同じx
です。
次に、 のすべてのビットをループしx
、設定されている最初の最上位ビットで停止します。i
は に初期化され1000000000000000000000000000
、ループx & i
は がゼロ以外に評価されるまでそれを右シフトし続けます。その時点で最初の最上位ビットである が見つかりました1
。その時点で、 の補数を取ると、でi
このビットをオフにするマスクが生成されます。これは、 であった唯一のビット( の最上位ビットに対応する)を除いて、すべてのビットが 1 に設定された数値であるためです。したがって、これを AND すると、必要なものが得られます。x
~i
1
x
x
コードは移植可能です。特定の表現を前提としておらず、unsigned
32 ビットまたは 64 ビットであるという事実に依存していません。
更新:コメントを読んだ後、より詳細な説明を追加しています。
第 1 ステップ - 何をするのかを理解するx & (x-1)
:
ここでは、次の 2 つの可能性を考慮する必要があります。
x
1 ( .......0011001
)で終わる
x
.......0011000
0 ( )で終わる
最初のケースでは、右端のビットが 0 に設定されてx-1
いるだけであることが簡単にわかります。x
0011001 - 1 = 0011000
x & (x-1)
x-1
2 番目のケースでは、理解するのが少し難しいかもしれませんが、の右端のビットがx
0の場合、1x-1
がx
見つかるまで、最下位ビットから始めて、すべての 0 ビットが 1 ビットに切り替えられます。が 0 に変わります。
これは、これに慣れていない人にとってはトリッキーになる可能性があるため、例を挙げましょう。
1101011000 - 1 = 11101010111
何故ですか?0 で終わる 2 進数の前の数は、右端の位置に 1 つ以上の 1 ビットで埋められた 2 進数であるためです。のよう10101111101111 + 1
にインクリメントする場合、次の「空き」位置、つまり次の 0 位置をインクリメントして 1 に変換する必要があり、その位置の右側にあるすべての 1 ビットが 0 に変換されます。 . これは、すべての base-n のカウント方法です。唯一の違いは、base-2 の場合は 0 と 1 しかないことです。
基数 10 のカウントがどのように機能するかを考えてみてください。桁がなくなると、値がラップアラウンドし、左側に新しい桁が追加されます。後は何999
ですか?さて、カウントが再びリセットされ、左側に新しい数字が追加され、9 が 0 に戻り、結果は1000
. バイナリ演算でも同じことが起こります。
バイナリでカウントするプロセスについて考えてみてください。0 と 1 の 2 ビットしかありません。
- 0 (10 進数の 0)
- 1 (10 進数の 1 - 現在、ビットが不足しています。次の数値では、この 1 は 0 に変わり、左側に新しいビットを追加する必要があります)
- 10 (10 進数 2)
- 11 (10 進数の 3 - プロセスが再び繰り返されます - ビットがなくなったので、これらの 2 ビットは 0 になり、左側に新しいビットを追加する必要があります)
- 100 (10 進数 4)
- 101 (10 進数の 5)
- 110 (同じプロセスが再び繰り返されます)
- 111
- ...
パターンが私が説明したとおりであることがわかりますか?
が0でx
終わる2番目のケースを考えていることを思い出してください。したがって、同じままである部分は、0 に変わった 1 の左側の部分だけです。x-1
x
x
x-1
x
x-1
x
したがって、最初の右端の 1 ビットがあった位置まではx & (x-1)
同じになります。x
これで、どちらの場合でも、x & (x-1)
実際には の右端の 1 ビットが削除されることがわかりx
ます。
2 番目のステップ: 正確には何~0U >> 1
ですか?
文字U
はの略ですunsigned
。int
C では、指定しない限り、整数定数は型になります。U
整数定数にaを追加すると、符号なしになります。これを使用したのは、前述したように、右シフトが符号拡張を行うかどうかは実装定義であるためです。単項演算子~
は補数演算子であり、数値を取得し、その補数を取ります。0 ビットごとに 1 になり、1 ビットごとに 0 になります。つまり、~0 は 1 で満たされた数値です11111111111...
。次に、それを 1 桁右にシフトすると、次のよう01111111....
になります。これを表す式は です~0U >> 1
。最後に、その補数を取って を取得します。100000....
これはコードでは~(~0U >> 1)
です。これは、左端のビットを 1 に設定し、その他すべてのビットを 0 に設定して数値を取得する移植可能な方法です。
K&R の第 2 章、より具体的にはセクション 2.9 を参照してください。48 ページからは、ビット単位の演算子が示されています。練習問題 2-9 では、なぜx & (x-1)
機能するのかを説明するよう読者に求めます。ご存じないかもしれませんが、K&R は C の生みの親である Kernighan と Ritchie によって書かれた C プログラミング言語について説明した本です。本のタイトルは「The C Programming Language」です。第 2 版を入手することをお勧めします。 . すべての優れた C プログラマーは、この本から C を学びました。