ビット操作の擬似言語

科目B応用問題で出題されるビット操作。フラグ管理・偶奇判定・XOR暗号などのパターンを擬似言語で読みこなします。

日野 こむぎ

ビット操作の擬似言語って、どんな書き方になるの?

藤森 さやか 先生

擬似言語ではビット演算を「論理積」「論理和」「排他的論理和」「シフト」と書くの。
具体的に見ましょう。

青木 澪

代表的な操作と擬似言語の対応:

/* 偶奇判定: 最下位ビットが0なら偶数 */
○ 手続: isEven(整数型: n)
  if ((n 論理積 1) = 0)
    return 真
  else
    return 偽
  endif

/* 特定ビットを立てる (8ビット中、3ビット目を1に) */
○ 手続: setBit3(整数型: n)
  return n 論理和 (1 を 2 ビット左シフト)   /* 0000 0100 とのOR */

/* 特定ビットをチェック (3ビット目が1か?) */
○ 手続: checkBit3(整数型: n)
  if ((n 論理積 (1 を 2 ビット左シフト)) ≠ 0)
    return 真
  else
    return 偽
  endif

桃井 すみれ

ビットマスクって便利ですねぇ

青木 澪

そうなの、特定の位置のビットだけを操作できるのよ。
フラグ管理やパーミッション、ネットワークマスクなどで多用されるの。

藤森 さやか 先生

もう一つ典型的な例: XOR の性質を利用した値交換 (一時変数なし):

/* XOR を使った値交換 (古典トリック) */
○ 手続: swapXOR(整数型: a, 整数型: b)
  a ← a 排他的論理和 b
  b ← a 排他的論理和 b   /* a^b ^ b = a になる */
  a ← a 排他的論理和 b   /* a^b ^ a = b になる */
  /* 結果: a と b の値が交換される */

日野 こむぎ

おぉっ!
一時変数なしで交換できるなんて魔法みたい!
あたし、感動しちゃった!

青木 澪

XORの性質「A^A=0」「A^0=A」を利用しているんです。
理論的には美しいんですが、現代の最適化コンパイラでは普通の swap のほうが速かったりしますね。

藤森 さやか 先生

試験では「次のビット演算の結果を求めよ」「ビットフラグの操作後の値は?」といった問題が出るのよ。