基本情報 平成30年度 春期 問2：テクノロジ系に関する問題

答えは c「論理積（AND）」 です。

ビット操作を順に追ってみます。例：A=00101000（最も右の1を残したい）

• 手順1: A − 1 = 00100111（最右1の位置以下が反転）
• 手順2: A XOR B = 00001111（変化した部分だけ1になる）
• 手順3: A AND C = 00001000 ← 最右の1だけ残る ✨

AND（論理積）は「両方1のところだけ1」。これで最右の1ビットだけ取り出せます。

👉 覚え方：ANDは絞り込み・XORは差分・ORは合体！

なぜこれが正解か

正解は c。例 A = 00101000 で手順を追う：

• 手順1：B = A − 1 = 00100111（最右の1がある桁以下が反転する）
• 手順2：C = A XOR B = 00001111（A と B で値が変わったビットが1）
• 手順3：D = A AND C = 00101000 AND 00001111 = 00001000（最右の1だけ残り、他は0）

AND演算は「両ビットが1なら1」なので、Cで1になっている範囲かつ元のAでも1のビット＝最右の1のみが残る。

各選択肢の解説

• a XOR：A XOR C は最右の1を消してしまう。
• b NAND：（A AND C）の否定なので逆の結果。
• c AND：上記の通り正しい結果 → 正解。
• d OR：A OR C はC の1範囲を全て1にしてしまう。

覚え方・ひっかけ注意

ビット操作技法：「X AND (-X) で最右1ビット取得」は競技プログラミング頻出のテクニック。本問の手順は事実上 X AND (-X) と等価（2の補数で −X = ~(X−1) = NOT(X)+1）。論理演算の真理値表は完璧に暗記する必要あり。

理論的背景

本問はビット操作（bit manipulation）の古典イディオム「最下位ビット（LSB）の1だけ抽出」。

X AND (-X) = X AND (~X + 1) = 最下位の1ビットのみ残る

2の補数表現で −X = ~X + 1。X − 1 = X XOR (最下位の1以下が連続して反転)。本問の3手順は実質的にこの数式を分解して実装している。

関連イディオム

• 最下位の1ビットを消す：`X & (X - 1)`。Brian Kernighan アルゴリズム（popcount）の中核。
• 2のべき乗判定：`X & (X - 1) == 0`（ただしX != 0）。
• ビットカウント（popcount）：`while(X) { count++; X &= X - 1; }` で立っているビット数を高速算出。CPU 命令（x86の POPCNT、ARMの VCNT）にも実装。
• 最上位ビット抽出：`LSB` は逆操作の `MSB` で代用するのが複雑、`__builtin_clz`（count leading zeros）等を使う。
• ビットセット／クリア／トグル：`X |= (1<<n)`, `X &= ~(1<<n)`, `X ^= (1<<n)`。

用途

• フェニック木（Binary Indexed Tree、Fenwick tree）：累積和の動的更新を O(log n) で行う、最下位1ビット移動で実装。
• メモリアラインメント：2のべき乗境界判定、アライン補正。
• CRC、巡回符号：ビット演算で多項式演算を実装。
• 暗号アルゴリズム：AES、SHAなどの内部処理。
• 圧縮（Huffman、ANS）：ビットストリーム操作。
• グラフィックス：マスク、Z バッファ、アルファブレンディング。
• デバイス制御：レジスタの特定ビット操作（組込み系）。

CPU 命令

• BSF/BSR（x86）：Bit Scan Forward/Reverse、最下位/最上位1ビット位置取得。
• POPCNT（x86 SSE4.2）：ビットカウント1命令。
• TZCNT/LZCNT（BMI1）：trailing/leading zero count。
• PDEP/PEXT（BMI2）：パラレル ビット ディポジット/エクストラクト。
• PSHUFB/VPSHUFB（SSSE3/AVX2）：SIMD ビット並べ替え。

試験での位置づけ

FE「基礎理論／ビット演算」分野の頻出パターン。論理演算の真理値表、ビット演算による高速化テクニック、補数表現はセットで習得。応用情報・エンベデッド・データベーススペシャリストでは具体応用（CRC計算、Bloom filter、ハッシュ実装）まで踏み込む。

選択肢の発展補足

bのNANDは計算機の機能完全集合（universal gate）。NAND だけで全論理関数を構成可能。NORも同様。実際のIC設計ではNAND/NORが基本セルとして多用される（FPGAのLUTもこれを内部実装）。aのXORは加算器（半加算器、全加算器）の中核論理、暗号でワンタイムパッドの基本演算。dのORはビットマスクのセット操作で頻用。