第108回 コンプリメント・コンプレックス(後編)

「ねえ、お兄ちゃん。この計算すると、何が出てくると思う?」とユーリが言った。
$ \newcommand{\BAR}[1]{\bar{#1}} \newcommand{\BAND}{\mathrel{\&}} \newcommand{\NEQ}{\neq} \newcommand{\LEQ}{\leqq} \newcommand{\LEQX}{\preceq} \newcommand{\ORX}{\vee} \newcommand{\ANDX}{\wedge} \newcommand{\CUP}{\cup} \newcommand{\CAP}{\cap} $
登場人物紹介
:数学が好きな高校生。
ユーリのいとこの中学生。のことを《お兄ちゃん》と呼ぶ。

僕の部屋

ユーリは、双倉図書館で先日行われたイベントで、コンピュータの計算をリサから教えてもらった。 今日は先生役になって、にいろいろクイズを出してくる。

いまは、ビットパターンを使って《 $2$ の補数表現》について話しているところ。

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

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

《 $4$ ビットのビットパターンと、 $2$ の補数表現》
$$ \begin{array}{rr} \text{ビットパターン} & \text{ $2$ の補数表現} \\ \hline 0000 & 0 \\ 0001 & 1 \\ 0010 & 2 \\ 0011 & 3 \\ 0100 & 4 \\ 0101 & 5 \\ 0110 & 6 \\ 0111 & 7 \\ 1000 & -8 \\ 1001 & -7 \\ 1010 & -6 \\ 1011 & -5 \\ 1100 & -4 \\ 1101 & -3 \\ 1110 & -2 \\ 1111 & -1 \\ \end{array} $$

クイズ

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

クイズ
次の式は何を作るか。
$$ n \BAND -n $$

「これは?」

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

「わかるかといわれても……この $\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 \BAND -n $$

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

ユーリ「そだね」

$n = 0$ の場合 $$ \begin{array}{ccccclll} & 0 & 0 & 0 & 0 & \cdots & (0)_{10} \\ \& & 0 & 0 & 0 & 0 & \cdots & (-0)_{10} \\ \hline & 0 & 0 & 0 & 0 \\ \end{array} $$

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

$n = 1$ の場合 $$ \begin{array}{ccccclll} & 0 & 0 & 0 & 1 & \cdots & (1)_{10} \\ \& & 1 & 1 & 1 & 1 & \cdots & (-1)_{10} \\ \hline & 0 & 0 & 0 & 1 \\ \end{array} $$

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

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

はしばらく計算を続けて表を作った。
$$ \begin{array}{cccl} n & -n & n \BAND -n \\ \hline 0000 & 0000 & 0000 & \text{ $n = 0$ のとき} \\ 0001 & 1111 & 0001 & \text{ $n = 1$ のとき} \\ 0010 & 1110 & 0010 & \text{ $n = 2$ のとき} \\ 0011 & 1101 & 0001 & \text{ $n = 3$ のとき} \\ 0100 & 1100 & 0100 & \text{ $n = 4$ のとき} \\ 0101 & 1011 & 0001 & \text{ $n = 5$ のとき} \\ 0110 & 1010 & 0010 & \text{ $n = 6$ のとき} \\ 0111 & 1001 & 0001 & \text{ $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 & \text{ $n = 1$ のとき} \\ 0011 & 1101 & 0001 & \text{ $n = 3$ のとき} \\ 0101 & 1011 & 0001 & \text{ $n = 5$ のとき} \\ 0111 & 1001 & 0001 & \text{ $n = 7$ のとき} \\ \end{array} $$

ユーリ「……」

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

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

「?」

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

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

は表をにらんで考える。 $n \BAND -n$ は何を表してる?
$$ \begin{array}{cccl} n & -n & n \BAND -n \\ \hline 0000 & 0000 & 0000 & \text{ $n = 0$ のとき} \\ 0001 & 1111 & 0001 & \text{ $n = 1$ のとき} \\ 0010 & 1110 & 0010 & \text{ $n = 2$ のとき} \\ 0011 & 1101 & 0001 & \text{ $n = 3$ のとき} \\ 0100 & 1100 & 0100 & \text{ $n = 4$ のとき} \\ 0101 & 1011 & 0001 & \text{ $n = 5$ のとき} \\ 0110 & 1010 & 0010 & \text{ $n = 6$ のとき} \\ 0111 & 1001 & 0001 & \text{ $n = 7$ のとき} \\ \end{array} $$

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

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

ユーリ「答えは?」

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

《クイズの答え(「僕」)》
$n \BAND -n$ は、 $n = 2^m\times\text{奇数}$ の形にしたときの $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} $$

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

「ユーリの答えって?」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

hyuki Web連載「 後編03/28 15:51まで https://t.co/YpXip7mr66 5年弱前 replyretweetfavorite

brv00 |数学ガールの秘密ノート|結城浩|cakes(ケイクス) https://t.co/gjSkNzyEtx リサがいないとちゃん付けし放題ですね(ぉ 5年弱前 replyretweetfavorite

hyuki 今日は過去記事の無料リンクです! 5年弱前 replyretweetfavorite

fall_twtr 遅ればせながら読了。ルーラー関数、n&-n…初めて知った。どんどん話が広がって、非常に面白い! 5年弱前 replyretweetfavorite