基本情報技術者 2018年 秋期 午前（科目A） 問02

最右の1を残すビット操作のアルゴリズム【午前2 解説】

要点まとめ

• 結論: 手順3に入る論理演算は論理積(AND)で、A & (A XOR (A-1)) によって最右の1だけが残る。
• 根拠: Aから1を引くと最右の1が0に、下位ビットが1に反転し、XORはその位置と下位を1にするためANDで唯一の1になる。
• 差がつくポイント: A-1によるビット反転のパターンと A&(A-1)、A&-A の関係を理解すれば素早く正解へ到達できる。

正解の理由

• B = A - 1 はその最右の1を0にし、下位 k ビットをすべて1にします（B = X 0 1^k）。
• C = A XOR B は位置 k とその下位 k ビットが1になります（C = 0...1 1^k）。
• 最後に A AND C を取ると、A が下位 k ビットで0であるため、A に元々あった上位の1は消え、位置 k の1だけが残ります。
  この操作により入力の最右の1のみが抽出されます。数式的には $A\&(A\oplus (A-1))$ が求める値です。

よくある誤解

• XOR を使えばよいと考える誤り: C は既に A XOR (A-1) なので、さらに A XOR C をすると下位ビットも残ったり消えたりして正しい単一ビットにならない。
• OR や NAND を試す誤り: OR は下位の1 もすべて含めてしまい、NAND は否定を伴うため反転ビットが混ざって意図した結果にならない。
• A=0 を考慮しない: 問題は「少なくとも一つは1」が前提だが、A=0 のときの扱い（結果は0）が試験的に問われる場合がある。

解法ステップ

1. 問題の手順を小さな例で実行して挙動を確認する（例: A=00101000）。
2. A-1 の効果を理解する（最右の1を0にしてそれより下位を1にする）。
3. XOR により「最右の1 と その下位ビット」が1になることを確認する。
4. 最後に AND を取ると A の上位ビットは消え、最右の1 だけが残ることを論理的に示す。
5. 選択肢と照合して、論理積(AND)が正しいことを確定する。

選択肢別の誤答解説

• ア: 排他的論理和(XOR) — A と C を XOR すると下位ビットのパターンが残ってしまい、単一の最右ビットにならない。
• イ: 否定論理積(NAND) — NAND は AND の否定であり、得たい単一ビットを得るどころかビット反転が入るため不適。
• ウ: 論理積(AND) — 正解。A&(A XOR (A-1)) が最右の1のみを抽出するため最適。
• エ: 論理和(OR) — OR は下位の1も含めてしまい、最右の1以外も1になってしまう。

補足コラム

• よく使われるビットトリック: 最右の1を取り出す別表現として $A\&(-A)$（2の補数を使う方法）があり、$A\&(A\oplus (A-1))$ と同じ結果になります。
• 証明のスニペット（Python）:

def isolate_rightmost_one(a):
    return a & (a ^ (a - 1))

for a in [0b00101000, 0b10110000, 0b00000100]:
    print(bin(a), '->', bin(isolate_rightmost_one(a)), 'using A&(A^(A-1))')
    print(bin(a), '->', bin(a & -a), 'using A&-A')

• また、A & (A-1) は「最右の1を0にする」操作として知られており、これらの関係を覚えておくと問題解答が速くなります。

FAQ