第108回 シーズン11 エピソード8

コンプリメント・コンプレックス（後編）

僕の部屋

ユーリ「これで納得。 $2$ の補数表現で、 $x$ から $−x$ を作るには《ビット反転して $1$ 足す》んだね（第107回参照）」

僕「それにしても、よくできているなあ」

クイズ

ユーリ「それから、リサ姉（ねー）から、こんなクイズもらってきたよ」

僕「これは？」

ユーリ「さー、わかるかにゃ？」

僕「わかるかといわれても……この $\BAND$ はどんな演算子？」

ユーリ「あー、そかそか。あのね、 $\BAND$ は《ビット単位の論理積》だって」

僕「ああ、なるほど。and（かつ） なのか。 ということは……ビット単位でこういう計算をすればいいんだね」

$$ \begin{align*} 0 \BAND 0 &= 0 && \\ 0 \BAND 1 &= 0 && \\ 1 \BAND 0 &= 0 && \\ 1 \BAND 1 &= 1 && \\ \end{align*} $$

ユーリ「そだよん。《両方が $1$ のときだけ $1$ になる》って言ってた」

僕「$n$ を《$2$ の補数表現》で考えて、 $n \BAND -n$ の計算をするんだね」

ユーリ「うん」

僕「それは、クイズでも何でもなくて、ただ計算問題じゃないのかな。 たとえば、そうだなあ、 $n = 6$ のときを考えてみようか。 $n = 6$ のビットパターンは $0110$ で、 $-n$ つまり $-6$ のビットパターンは $1010$ だ。 この二つのビットパターンの $\BAND$ を計算すると、《両方が $1$ のときだけ $1$ になる》だから……」

$$ \begin{array}{ccccclll} & 0 & 1 & 1 & 0 & \cdots & (6)_{10} \\ \& & 1 & 0 & 1 & 0 & \cdots & (-6)_{10} \\ \hline & 0 & 0 & 1 & 0 \\ \end{array} $$

僕「……だから結果は $0010$ になる」

ユーリ「さー、お兄ちゃん！　このクイズの謎、解けた？　ねー解けた？」

僕「いま、たった一つだけ計算したばかりじゃないか。まだ何にもわからないよ。 というか、ユーリは答えをリサちゃんから聞いてきたの？」

ユーリ「もちろんさ！　あのね、おもしろいんだよ。この式 $n \BAND -n$ はね……」

僕「ちょっと待った！　そんなに答えを急ぐなよ。考えるから」

ユーリ「ちぇっ！」

僕「《$n$ が出てきたら、小さな数でやってみる》というセオリーにしたがって考えよう。 さっきは試しに $n = 6$ でやってみたけど、あらためて $n = 0$ から。 $n$ も $-n$ も $0000$ だから、 $n \BAND -n$ も $0000$ だね」

ユーリ「そだね」

僕「$n = 1$ のときは、 $n$ は $0001$ で、 $-n$ は $1111$ だから、 $n \BAND -n$ は $0001$ になる」

ユーリ「ねー、わかった？　わかった？」

僕「よっぽど答え言いたいんだな、ユーリ」

$$ \begin{array}{cccl} n & -n & n \BAND -n \\ \hline 0000 & 0000 & 0000 & \REMTEXT{$n = 0$のとき} \\ 0001 & 1111 & 0001 & \REMTEXT{$n = 1$のとき} \\ 0010 & 1110 & 0010 & \REMTEXT{$n = 2$のとき} \\ 0011 & 1101 & 0001 & \REMTEXT{$n = 3$のとき} \\ 0100 & 1100 & 0100 & \REMTEXT{$n = 4$のとき} \\ 0101 & 1011 & 0001 & \REMTEXT{$n = 5$のとき} \\ 0110 & 1010 & 0010 & \REMTEXT{$n = 6$のとき} \\ 0111 & 1001 & 0001 & \REMTEXT{$n = 7$のとき} \\ \end{array} $$

僕「$-7$ までしか表せないから、これで表はできた……なるほど、パターンがわかってきたよ。 《$n = 0$ を除くと、どんな $n$ に対しても $n \BAND -n$ の計算結果で $1$ になるビットはひとつだけ》だね。 $0001$ とか、 $0010$ とか」

ユーリ「よいところに気付いたにゃ。それで、ファイナルアンサー？」

僕「いやいや、まだまだ。《$1$ になるビットはひとつだけ》というのは、 手がかりの一つに過ぎないよ。 パターンを見てみると、 $n = 1,3,5,7$ のときには、 $n \BAND -n$ は必ず $0001$ になってることがわかる」

$$ \begin{array}{cccl} n & -n & n \BAND -n \\ \hline 0001 & 1111 & 0001 & \REMTEXT{$n = 1$のとき} \\ 0011 & 1101 & 0001 & \REMTEXT{$n = 3$のとき} \\ 0101 & 1011 & 0001 & \REMTEXT{$n = 5$のとき} \\ 0111 & 1001 & 0001 & \REMTEXT{$n = 7$のとき} \\ \end{array} $$

ユーリ「……」

僕「そして、 $n = 0,2,4,6$ のときには $0001$ にはならない。 だから、《$n$ が奇数のときに限り、 $n \BAND -n$ のビットパターンは $0001$ になる》 といえる」

ユーリ「……ねーお兄ちゃん。そんなのは表見ればわかることじゃん？　もっと、 シャキーンと答えてよ」

僕「？」

ユーリ「だからさー、 $n \BAND -n$ とゆーのは《ナントカ》だ！って答えないと」

僕「まあ、そりゃそうだな。うーん……」

$$ \begin{array}{cccl} n & -n & n \BAND -n \\ \hline 0000 & 0000 & 0000 & \REMTEXT{$n = 0$のとき} \\ 0001 & 1111 & 0001 & \REMTEXT{$n = 1$のとき} \\ 0010 & 1110 & 0010 & \REMTEXT{$n = 2$のとき} \\ 0011 & 1101 & 0001 & \REMTEXT{$n = 3$のとき} \\ 0100 & 1100 & 0100 & \REMTEXT{$n = 4$のとき} \\ 0101 & 1011 & 0001 & \REMTEXT{$n = 5$のとき} \\ 0110 & 1010 & 0010 & \REMTEXT{$n = 6$のとき} \\ 0111 & 1001 & 0001 & \REMTEXT{$n = 7$のとき} \\ \end{array} $$

ユーリ「ねー、わかった？　降参？　答え言ってもいい？」

僕「いや、まだまだ……よし、わかったよ、ユーリ」

ユーリ「答えは？」

僕「$n \BAND -n$ は、 《$n = 2^m\times\REMTEXT{奇数}$の形にしたときの$2^m$を表している》 だね。 $n = 0$ は除くけど」

ユーリ「え？　どゆ意味？」

僕「その通りの意味だよ。たとえば、 $n = 6$ を考えてみよう。 $6 = 2^1 \times 3$ と書けるから、 $2^m$ に相当するのは $2^1 = 2$ だ。 それに対して、 $n \BAND -n$ のビットパターンは $0010$ で、これは $2$ 進数で $2$ を表している」

ユーリ「え……」

僕「うん、そうだよ。さっき言った《$n$ が奇数のときに限り、 $n \BAND -n$ のビットパターンは $0001$ になる》というのにも、 ぴったり合ってる。 $n$ が奇数だったら、 $n = 2^0 \times 1$ という形になる。 $2^m$ に相当するのは $2^0 = 1$ だね。 それに対して、 $n \BAND -n$ のビットパターンは $0001$ で確かにこれは $2$ 進数で $1$ を表している。 さっきの表のビットパターンを $10$ 進数で表してみるとわかるよ。 $0$ を除外してみると、どちらも $1,2,1,4,1,2,1$ となる」

$$ \begin{array}{lll} n & 2^m & n \BAND -n \\ \hline 0 & & 0 \\ 1 = 2^0 \times 1 & 2^0 = 1 & (0001)_2 = 1 \\ 2 = 2^1 \times 1 & 2^1 = 2 & (0010)_2 = 2 \\ 3 = 2^0 \times 3 & 2^0 = 1 & (0001)_2 = 1 \\ 4 = 2^2 \times 1 & 2^2 = 4 & (0100)_2 = 4 \\ 5 = 2^0 \times 5 & 2^0 = 1 & (0001)_2 = 1 \\ 6 = 2^1 \times 3 & 2^1 = 2 & (0010)_2 = 2 \\ 7 = 2^0 \times 7 & 2^0 = 1 & (0001)_2 = 1 \\ \end{array} $$

ユーリ「ユーリの答えと違う……」

僕「ユーリの答えって？」