(71.1) 1 ビットには 0 か 1 のどちらか一方が格納できる。 Ｃ言語の規格において、int 型は最低で 16 ビットと決められている。 センターの linux では 32 ビットである。 それらのビットは左右に一列に並んでいると考える。 int 型に非負の数を格納する場合、二進法による表現で格納される。 たとえば十進の 53 は 0000 0000 0000 0000 0000 0011 0101 として格納されている。 （途中の空白は見やすくするためにおいただけのもの。）
(71.2) ※ 「二進法による表現」は「二進表現」「二進表記」「二進表示」、あるいは単に「二進」ともいうが、 これらはすべて同じもので、実数を 0 と 1 と小数点だけで書く方法の一つを指す。 「二進数」というものも存在するが、これは普通の数とは異なる数学的対象である。 世間では二進法で表現された数のことを間違って“二進数”と呼んでいることがあるが、 数学科の諸君は混同しないように。 二進数はおそらく３年後期の代数学の時間に習うと思う。
(71.3) 次のプログラムで、入力した整数がどのようなビット列で格納されたかを見ることができる。 （ただし、表示するのは下の 15 ビットのみなので、0 から 215 - 1 = 32767 まで。）
#include <stdio.h>
main() {
int x, mask;
printf("整数を入力してください.\n");
scanf("%d", &x);
for (mask = (2*2*2*2)*(2*2*2*2)*(2*2*2*2)*(2*2); mask != 0; mask = mask >> 1) {
if ((x & mask) != 0) {
printf("1");
} else {
printf("0");
}
}
printf("\n");
}
(71.4) ビットごとの論理演算子を三つ紹介する。1 が真を、0 が偽を表す。
|
|
|
| |||||||||||||||||||||||||||||||||
(71.5) 例：6 & 5 は、それぞれを二進で書くと 110, 101 だから
110 101 ----- 100より 4 となる。
(71.6) XOR は、exclusive or に由来した名前であると思われる。 両方とも 0 または両方とも 1 のビットについては 0, 片方のみ 1 のビットについては 1 とするもの。 各ビットごとに mod 2 で足し算をしていると思えばよい。 よって、 群論で出てきた位数 2 の巡回群 Z/2Z がビットの数だけ直和になっているもの、 とみなしたときの演算である。
(71.7) 以上の三つの演算は、交換法則、結合法則を満たす。
(71.8) 「>>」, 「<<」 は「シフト演算子」と呼ばれる。 たとえば 23 >> 2 は 23 を二進で書いて 10111, これを右に 2 だけシフトするので 101 となって、 十進で答えを書けば 5 となる。 4 で割って余りを切り捨てるのと同じである。 23 << 2 は 10111 を左に 2 だけシフトして 1011100, すなわち十進で 92 となる。 4 倍するのと同じである。
(71.9) 上のプログラム例のように、1 つのビットだけが立っている（＝ 1 である） 変数 mask を用いて x & mask とすると、x のビットのうち、 mask で立っているビットと同じ位置のビットが立っていれば 0 でない数 （実は mask と等しい）が、立っていなければ 0 が得られる。
x 0000 0000 0011 0101 x 0000 0000 0011 0101 mask 0000 0000 0001 0000 mask 0000 0000 0000 1000 ------------------------------- ------------------------------- x & mask 0000 0000 0001 0000 x & mask 0000 0000 0000 0000
(71.10) 1 つのビットだけが立っている変数 mask を用いて x | mask とすると、x のビットのうち、 mask で立っているビットと同じ位置のビットを立てた数になる。 （元々立っていればそのまま。）
x 0000 0000 0011 0101 x 0000 0000 0011 0101 mask 0000 0000 0001 0000 mask 0000 0000 0000 1000 ------------------------------- ------------------------------- x | mask 0000 0000 0011 0101 x | mask 0000 0000 0011 1101
(71.11) 「^」は、x が 0 か 1 の値をとるとき、 x = x ^ 1 とすることで x の値を反転させる （＝ 0 なら 1 に、1 なら 0 にする）ことができる。
(71.12) 「~」はビットごとの反転演算子である。 int 型が 16 ビットだったとすると、次のようになる。
x 1010 1110 0011 1011 ------------------------ ~x 0101 0001 1100 0100
(71.13) 以上の演算子の優先順位は直感と異なる。 たとえば & は != より低い。 そのため、(71.3) のプログラムで if の中は (x & mask) != 0 と小カッコをつけてあるのである。 くわしくは K&R2 §2.12 の表を参照。
(71.14) われわれにとっては加減乗除のほうがこれらの演算子よりも身近に感じられるが、 計算機にとってはこれらの論理演算子のほうが基本的であり、 それらの組み合わせで加減乗除を実現している（と思われる）。
(71.15) （練習）： x と y の和を返す関数 int add(int x, int y) を、加減乗除を使わずに書いてみよ。 （ヒント： 小学校で習った、十進の場合の足し算と同じである。 x と y を、下から 1 ビットずつ見てゆく。
for (mask = 1; mask != 0; mask = mask << 1) {
...
}
のようになる。
答えを入れる変数と、繰り上がりを覚えておく変数も、必要なら用意せよ。）
(72.1) 次の事実を用いる。 「三つの山の石の個数を a[0], a[1], a[2] とする。 もしも a[0] ^ a[1] ^ a[2] が 0 の状態で相手の番になると、 相手がどう石をとってもこの式の値は 0 でなくなり、 次に自分はうまく石をとることでこの式の値を 0 にできる。すなわち、 またこの式を 0 にして相手の番にできる」。
(72.2) 証明： たとえば、三つの山の石の数が 3, 5, 6 のとき、
a[0] 0011
a[1] 0101
a[2] 0110
---------------------------
a[0] ^ a[1] ^ a[2] 0000
なので a[0] ^ a[1] ^ a[2] は 0 である。相手が石をとると、
a[0], a[1], a[2] のうちのどれか一つについて、
あるケタの数が変わる。すると、
a[0] ^ a[1] ^ a[2] のそのケタが変わるから、1 が出てくる。
(72.3) a[0] ^ a[1] ^ a[2] が 0 でない状態で自分の番になったとする。 その値を x としよう。 x がどんな値でも x ^ x は 0 であることに注意すると、 (a[0] ^ a[1] ^ a[2]) ^ x は 0 であることがわかる。 「^」は交換法則、結合法則を満たすので、 この式は (a[0] ^ x) ^ a[1] ^ a[2] に等しいから、 もしも a[0] ^ x が a[0] より小さいなら、 自分は第 0 の山から a[0] - (a[0] ^ x) 個の石をとって、 a[0] を a[0] ^ x にすればよい。 よって、あとは次を示せばよいことになる。
(72.4) i が 0, 1, 2 のうちどれかは、a[i] ^ x が a[i] より小さい。 このことは、次のように示される。 x を二進表記したとき、一番左の 1 のあるケタは、 a[0], a[1], a[2] のうちどれかが 1 となっている。 そのような a[i] を選べば、 a[i] ^ x のそのケタは 1 から 0 に変わり、 それより左のケタは変わらないので、 a[i] ^ x は a[i] よりも小さくなる。 ［証明終わり］
(72.5) このようにして石をとってゆくとき、 三つの石の個数の和はどんどん小さくなってゆくから、いつか 0 になる。 そのとき、a[0] ^ a[1] ^ a[2] の値は 0 であるから、 相手の番である。 ということは、自分の勝ちである。
(72.6) （注意） 上の証明では、(72.4) のようにして石をとるべき山を選んだが、 実際には、a[i] ^ x を計算してみて a[i] より小さかったらその山からとる、 とすればよい。
(72.8) （練習）この必勝法に基いてユーザと三山崩しを戦うプログラムを書いてみよ。
(72.9) ※ 山の番号と、とる石の数をいっぺんに入力できたほうが遊びやすいであろう。 それには、
scanf("%d %d", &i, &n);
のように書く方法がある。
これでユーザが「2 5」と入力すると、
i に 2 が、n に 5 が入力される。
二重引用符の中の二つの %d の間にスペースがあるので、
入力時にも間にスペースを入れて区切って入力することになる。
スペースの個数はいくつでも構わない。
ただし、間違って間にカンマを打ったりすると……。
（恐ろしくてとても言えないわけではないが、自分で試してみること。
どうなるかは、コンパイラによって異なるようである。）
(72.10) ※ 山が一つで、そこから１〜３個の石をとり合うゲームだと、 mod 4 で 0 にして相手に渡すのが必勝法となる。 ある意味で、それと似ている。