ビット演算のテクニック

ビット演算でフラグの検査・変更、1 の個数、二の冪を調べられます。短い式でも各変化には理由があります。このレッスンは八ビット全体を表示して検証します。

権限や機能フラグのようにビット自体が意味を持つ時に使います。疎な集合は 1 を一つずつ訪ねられ、popcount(a ^ b) はハミング距離です。容量やアラインメントが二の冪を要求するなら、先にその条件を確認できます。

マスクは穴の開いた型紙です。AND は選択・保持、OR は 1 への設定、反転マスクとの AND は消去です。x - 1 は借りによって末尾を変えます。

最下位の 1 を消す

対象がビット k なら mask = 1 << k を作ります。k だけ 1 です。x & mask で検査、x | mask で設定、x & ~mask で消去します。

OR による設定は冪等で、元が 1 なら変わりません。消去は元に関係なく 0 にします。したがって設定後の消去が元に戻るのは、対象が元々 0 の場合だけです。

x & (x - 1) は最下位のセットビットを消します。正整数から一を引くと、上位は不変、最下位の 1 は 0、その下の 0 は借りで 1 になります。元の x と AND を取れば上位を保ち、新しい下位の 1 は元の 0 で消え、最低の 1 だけがなくなります。0 までの反復数がセットビット数です。

正の二の冪は 1 が一つなので、判定は x > 0 and (x & (x - 1)) == 0。0 も後半の等式を満たすため、x > 0 が必要です。

操作をステップで追う

既定は x = 40 = 00101000、k = 2、mask = 00000100。

1. 40 & 4 = 0 なので、ビット 2 は元々 0。
2. 設定すると 00101000 | 00000100 = 00101100、44。同じマスクで再検査すると非零。
3. 可視八ビットの反転マスクは 11111011。00101100 & 11111011 = 00101000。元のビットが 0 だったので、この例は 40 に戻る。
4. 元の 40 から数え直す。40 - 1 = 39 = 00100111、40 & 39 = 32 = 00100000。最低の 1 が消え、カウント 1。
5. 32 - 1 = 31 = 00011111、32 & 31 = 0。カウント 2。二つの 1 に二反復。
6. 二の冪判定では最初の結果を再利用する。40 & 39 = 32 が非零なので 40 は違う。32 & 31 = 0 で 32 は正だから合格。
7. 0 は 0 & -1 = 0 を満たすが、0 > 0 が偽なので完全な判定は拒否する。

32 は受理、40 は複数の 1、0 は正でないことを理由に拒否します。

時間・空間計算量

固定幅の機械語なら、マスク作成、検査、設定、消去、二の冪判定は時間・追加空間とも O(1) です。

Kernighan のカウントは 1 ごとに一反復。セットビット数 p なら O(p) 時間、O(1) 空間です。W ビットでは p <= W なので最悪 O(W)。全位置走査は 1 が一つでも W 位置を調べます。

疎なフラグや各セット位置を処理する時に最低 1 の消去が役立ちます。単純な個数なら言語や CPU のネイティブ popcount も使えます。a ^ b の個数を取ればハミング距離です。

境界ケース

• x = 0：カウントは零反復、二の冪判定は false。
• x = 1：一つの 1 を一回で消し、二の冪と分かる。
• x = 255 = 11111111：八反復で、このレッスンの最大密度。
• k = 0、k = 7：最低位と左端の可視ビット。同じマスク式を使う。
• 対象がすでに 1：OR は変えないが、その後の消去は元のビットを失う。復元ではない。

よくある間違い

• x > 0 を省く。 0 & -1 が 0 なので、0 を誤って二の冪とします。
• XOR を消去に使う。 x ^ mask は 0 と 1 の交換です。必ず 0 にするなら x & ~mask。
• x & (x - 1) だけ暗記する。 借りが最低 1 と下位の接尾部をどう変え、AND がなぜ一つだけ消すかを確認します。
• 位置とマスクを混ぜる。 k = 2 は位置、1 << k = 4 が選択用のマスクです。

簡略化の範囲

入力は非負の 0–255、表示は下位八ビットです。Python は任意精度整数、JavaScript のビット演算は符号付き 32 ビットへ変換します。この範囲なら両コードの結果が一致します。範囲外の符号付きマスク、オーバーフロー、言語別のシフト動作は扱いません。