ビット演算の基礎

ビット演算は一つの整数に複数のフラグ、権限、詰めたフィールドを保存するために使います。AND はマスクの検査、OR はセット、XOR は反転、シフトは位置の調整です。このレッスンは符号なし 8 ビットの二数をそろえ、結果を同じ境界内に保ちます。

ビット演算の仕組み

二本の穴あきテープを重ねると考えてください。論理演算は同じ列の入力対だけを見ます。ビット 5 の値がビット 4 の判定を変えることはありません。

権限の一バイトは八つのスイッチを保存できます。permissions & READ_MASK は対象の位置を選び、ほかのフラグを変更しません。色やプロトコルのフィールドもマスクで選択し、シフトで読む位置へ移せます。

• AND：両方 1 の時だけ 1。
• OR：どちらかが 1 なら 1。
• XOR：二つが違えば 1。
• NOT：一入力の 0 と 1 を交換する。

シフトは位置を変えます。左はビット 7 へ、右はビット 0 へ移動し、境界を越えるビットは捨て、空いた位置を 0 で埋めます。

符号なし 8 ビットの範囲は 0–255、マスクは 11111111。NOT と左シフトの後にマスクし、下位八ビットを残します。

演算をステップで追う

既定は a = 181 = 10110101、b = 102 = 01100110、shift = 1。四種類の入力対がすべて含まれ、AND、OR、XOR の全規則を検査できます。

1. AND：ビット 7 から 0 へ調べ、両方 1 の列だけ残す。00100100 = 36。
2. OR：どちらか 1 なら残す。11110111 = 247。
3. XOR：不一致を 1、一致を 0。11010011 = 211。
4. NOT：b は使わず a の八ビットを反転。10110101 から 01001010 = 74。
5. 幅の確認：Python でも JavaScript でも、生の ~181 は -182。-182 & 0b11111111 は同じ AND 規則で下位八ビットを選び、01001010 = 74 にする。
6. 一ビット左シフト：元のビット 7 を捨て、0 に 0 を入れる。マスク後 01101010 = 106。
7. 一ビット右シフト：元のビット 0 を捨て、7 に 0 を入れる。01011010 = 90。

結果表は六つの答えを残します。論理演算は固定列内の判定、シフトは列の移動であり、境界で情報を失うことがあります。

時間・空間計算量

固定 8 ビットの機械演算は時間も追加空間も O(1)。アニメーションの各ビット走査は説明のためで、幅を W とすれば各論理演算の表示に O(W) 時間を使います。

任意精度整数では、必要な機械語の数に応じて実際の費用も増えます。任意長の入力まで O(1) としないでください。

境界ケース

• shift = 0：移動、破棄、ゼロ埋めがない。
• shift = 8：全元ビットが境界外となり、両シフトとも 00000000。
• a と b が等しい：XOR は全 0、AND と OR は入力と同じ。
• a と b が補数：AND は全 0、OR と XOR は全 1。
• a = 0 と a = 255：八ビットの NOT が両端値を交換する。

よくある間違い

• シフトを無条件に二倍・半分とする。 幅、符号、切り捨てを考慮します。高位が消える左シフトは通常の整数乗算と異なる結果になります。
• 回転だと思う。 << と >> は越えたビットを反対側へ戻しません。このモデルは破棄して 0 を入れます。
• NOT の整数モデルを忘れる。 Python は八ビットに限定されず、~181 は 74 でなく -182。& MASK が 255 と AND を取り、下位八ビットを選びます。
• 番号と画面方向を混同する。 左が 7、右が 0。セル上の番号で追います。

簡略化の範囲

プロセッサーはよく 8、16、32、64 ビット語を使い、言語ごとに符号付き表現と右シフトが異なります。ここでは符号なし八ビットに固定し、右は常にゼロ埋めです。算術右シフトや符号拡張は扱いません。