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

最右ビットの抽出ビット操作【午前解説】

正解の理由

• 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))$ が求める値です。

解法ステップ

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になってしまう。

よくある誤解

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

補足コラム

• よく使われるビットトリック: 最右の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