自然数が計算機の中で 2 進法により表現さ れていることは、みなさんご存じだろう。し かし、それ以外にも自然数の '0' と '1' の 列としての表現で有用なものが存在する。こ のコードは、グレイコードと呼ばれている。 2 進法は 0, 1, 10, 11 と始まる がグレイコードは、0, 1, 11, 10 と始まる。 一般に、2 進法では n 桁のコードを生成す るのに n 桁目を 1 にしてそこまでのコード を繰り返してたのに対し、グレイコードでは、 n 桁目を 1 にしてそこまでのコードを逆の 順番に用いている。つまり、新しい桁を 1 にしてそこまでのコードを対称に折り返す操 作を繰り返すことにより、このコードは生成 される。2 進コードからグレイコードへの変 換は簡単である。列を右に1文字シフトして、 元の列とビットごとの排他的論理和(異なれ ば 1、等しければ 0)をとればよ