基本情報技術者 2015年 春期 午前（科目A） 問01

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

正解の理由

解法ステップ

1. A を確認し、少なくとも1ビットが立っていることを前提とする。
2. B = A - 1 とする。A-1 は最右の1を0にし、それより下位のビットをすべて反転する。
3. C = A XOR B を計算すると、最右の1と下位全てが1になっているビットマスクが得られる。
4. A = A AND C を計算すると、AのうちCで1になっている位置だけが残り、最も右の1だけが抽出される。
5. 以上より a は「論理積（AND）」。

選択肢別の誤答解説

• ア: 排他的論理和（XOR）
  • 誤り。AとCをXORすると、Cの1がAで1でない部分まで影響し、複数ビットが立つ結果になり目的を達成しません。
• イ: 否定論理積（NAND）
  • 誤り。NANDはANDの否定であり、ビットマスクとして使うと反転した不必要な1が残るため不適切です。
• ウ: 論理積（AND）
  • 正解。AとCのANDは、Cが示す範囲（最右の1と下位）からAに元々あるビットだけを抽出し、結果的に最も右の1だけを残します。
• エ: 論理和（OR）
  • 誤り。ORを使うとCの領域すべてが1になり、最右の1以外のビットも1になってしまいます。

よくある誤解

• 「XORを使えば良い」と単純に思い込み、最後にAとCをXORしてしまうと複数ビットが残り正解になりません。
• Aが0の場合を考慮せずに「常に成り立つ」としてしまうと境界ケースで誤答になります（問題では少なくとも1つ1がある前提）。
• 2の補数や借りの発生によるビット反転の意味を理解していないと、なぜA-1が下位ビットを反転するかが混乱します。

補足コラム

// C の例
unsigned int lowbit = A & -A;

# Python の例（任意幅整数に対しても動作します）
lowbit = A & -A

FAQ