符号付き整数の代数的構造 - ペンギンは空を飛ぶ

数学の勉強に行き詰まったので、プログラミング関連で思い付いた小ネタについて書いてみる。

C言語でプログラミングをしたことがあれば、符号付き整数というものは扱ったことがあるだろう。例えばint型の変数とか、そういうものである。符号付き整数では負の数を扱う必要があるため、ビット列をそのまま2進数で表現された整数として解釈するわけにはいかず、表現したい整数との間に何らかの対応付けが必要となる。

先日、この符号付き整数の背後には何らかの代数的構造が潜んでいるのではないかと思い立った。本稿ではそれについて私が考えたことをまとめる。

準備

記号の導入

本稿では0, 1の並びにより表現されるビット列の集合について考える。ビット列に言及するとき、それがビット列であることが分かるように添字 $b$ を付ける。例えば、 $1011_b$ と書いたら、これは1, 0, 1, 1というビット列を意味する。ただし、変数に対して添字は付けない。

本稿で考えるビット列の長さは有限である。特に断らない限り、長さは全て $d \in \mathbb{N}$ であるとする。

全てのビットが0であるようなビット列は、簡潔のため、単に $0_b$ と書くことにする。また、最下位ビットだけ1で他が全て0であるようなビット列は、簡潔のため、単に $1_b$ と書くことにする。

ビット列 $a$ に対して、その全てのビットを反転させて得られるビット列を $\overline{a}$ と書く。特に、全てのビットが1であるようなビット列は $\overline{0_b}$ と書く。

0と1の割り当てについて

符号無し整数の場合、 $00...00_b, 00...01_b$ はそのまま整数の0, 1に対応する。符号付き整数の場合はこの後の議論を待たないとどのビット列をどの整数に割り当てるか決められないところだが、 $00...00_b, 00...01_b$ だけは符号無し整数の場合と同じく0, 1に割り当てることにする。

環としての構造

長さ $d$ のビット列を全て集めた集合 $S_d$ を考える。符号のことは一旦忘れて、ビット列を2進数で表現された整数であると見なせば、 $S_d$ の任意の2元に対して足し算を行うことが出来る。その和をさらに $2^d$ で割った余りを2進数で表せば、これは $S_d$ の元になる。このようにして $S_d$ に加法の演算を与えることが出来る。

乗法についても同様に与えることが出来る。結局、このようにして加法と乗法が与えられた集合 $S_d$ は $\mathbb{Z}/2^d \mathbb{Z}$ と同型な可換環になる。

イデアル

$S_d$ はどんなイデアルを持つだろうか？それを知るために、 $S_d$ と同型な環である $\mathbb{Z}/2^d \mathbb{Z}$ のイデアルについて考えてみよう。

対応定理[1]により、 $\mathbb{Z}$ のイデアルのうち $2^d \mathbb{Z}$ を含むものと、 $\mathbb{Z}/2^d \mathbb{Z}$ のイデアルは一対一に対応する。 $2^d \mathbb{Z}$ を含む $\mathbb{Z}$ のイデアルは以下の $d+1$ 個である。

$\displaystyle{ 2^d \mathbb{Z}, 2^{d-1} \mathbb{Z}, \cdots , 2 \mathbb{Z}, \mathbb{Z} }$

これらに対応する $\mathbb{Z}/2^d \mathbb{Z}$ のイデアルは以下の通りである。

$\displaystyle{ \begin{eqnarray} && \{0\}, \\ && \{0, 2^{d-1}\}, \\ && \cdots , \\ && \{0, 2, 4, \cdots, 2^d - 2\}, \\ && \mathbb{Z}/2^d \mathbb{Z} \end{eqnarray} }$

特筆すべきは、これら以外の部分集合はイデアルにならないということである。例えば、 $\mathbb{Z}/2^d \mathbb{Z}$ の元のうち3の倍数の集合はイデアルではない。

ただし、これはビット列をそのまま2進数で表現された整数であると見なした場合の話である。そのようなビット列と整数の間の対応関係の与え方はまさに符号無し整数そのものであるため、符号無し整数については $\mathbb{Z}/2^d \mathbb{Z}$ と全く同じことが言える。

では、符号付き整数の場合はどうであろうか？この時点ではまだ符号付きの場合のビット列と整数の対応付けについて述べていないため詳細は割愛するが、結論としてはやはり2の冪乗以外はイデアルの元とならない。

これは実際にプログラミングを行う際に注意が必要である。以下にこの重要性を示すためのサンプルコードと実行結果を示す。

サンプルコード：

#include <stdio.h>

int main()
{
    int a = 3;
    int b = 2000000000;
    int ab = a*b;

    printf("a = %d, b = %d, a*b = %d\n",
           a, b, ab);

    if(ab % 3 == 0){
        printf("ab can be divided by 3.\n");
    }else{
        printf("ab cannot be divided by 3.\n");
    }
    return 0;
}

実行結果：

a = 3, b = 2000000000, a*b = 1705032704
ab cannot be divided by 3.

ご覧の通り、3と他の整数の積を計算しているのに、その結果が3で割り切れないケースが存在する。

零因子

$d = 1$ の時、 $S_d$ は $F_2$ と同型な体になる。一方、 $d \ne 1$ の時は体どころか整域にすらならない。これも実際にプログラミングをする際には注意を要する事実である。例えば、2つのint型整数 $a, b$ に対して、どちらも0でないことを確かめるために $a * b$ が0かどうかチェックするのは誤りになる。

ここでの議論は符号付き整数・符号無し整数どちらについても成り立つ。符号の有無とはビット列の解釈の仕方の問題なのであって、環としての構造に違いはないためである。また、準備の章で $00...00_b$ は符号の有無に関わらず0に割り当てると決めたので、ビット列として考えても、符号化された整数として考えても、零因子を持つということに変わりはない。

このことを具体的に動くプログラムで確かめた結果を以下に示す。

サンプルコード：

#include <stdio.h>

int main()
{
    int a = 65536;
    int b = 196608;
    int ab = a*b;

    printf("a = %d, b = %d, a*b = %d\n",
           a, b, ab);

    if(ab == 0){
        printf("ab is 0.\n");
    }else{
        printf("ab is not 0.\n");
    }
    return 0;
}

実行結果：

a = 65536, b = 196608, a*b = 0
ab is 0.

ご覧の通り、0でない2つの整数の積が0になるケースがあることが分かる。

ビット列と符号付き整数の対応関係

ここからはいよいよ符号付き整数でのビット列と整数の対応付けの議論に踏み込んでいく。そのために、まずは以下のような写像 $n$ を考える。

$\displaystyle{ n : S_d \ni x \mapsto \overline{x} + 1_b \in S_d }$

以下でこの写像の性質について調べてみよう。

基本的性質

写像 $n$ について以下の式が成り立つ。

$x + n(x) = 0_b$
$n(n(x)) = x$
$n(x + y) = n(x) + n(y)$
$n(x)n(y) = xy$

以下で順に証明していく。

式1の証明

$\displaystyle{ \begin{eqnarray} x + n(x) &=& x + \overline{x} + 1_b \\ &=& \overline{0_b} + 1_b \\ &=& 0_b \end{eqnarray} }$

式2の証明

$\displaystyle{ \begin{eqnarray} n(n(x)) &=& \overline{n(x)} + 1_b \\ &=& \overline{\overline{x}+1_b} + 1_b \\ &=& \overline{\overline{x}+1_b} + (x + \overline{x} + 1_b) + 1_b \\ &=& \overline{\overline{x}+1_b} + (\overline{x} + 1_b) + x + 1_b \\ &=& \overline{0_b} + x + 1_b \\ &=& x \end{eqnarray} }$

式3の証明

$\displaystyle{ \begin{eqnarray} n(x+y) &=& \overline{x+y} + 1_b \\ &=& \overline{x+y} + (x + n(x)) + (y + n(y)) + 1_b \\ &=& \overline{x+y} + (x+y) + n(x) + n(y) + 1_b \\ &=& n(x) + n(y) \end{eqnarray} }$

式4の証明

$\displaystyle{ \begin{eqnarray} n(x)n(y) &=& n(x)n(y) + x(y+n(y)) \\ &=& n(x)n(y) + xy + xn(y) \\ &=& n(y)(n(x)+x) + xy \\ &=& xy \end{eqnarray} }$

それぞれの式の意味

上で述べた4つの式にはそれぞれ重要な意味がある。

まず、式1は $x \in S_d$ の加法による逆元が $n(x)$ であることを述べている。つまり、 $x$ を符号付き整数として見なしたとき、 $n(x)$ はその符号を反転したものだと解釈することができる。

次に式2だが、これは写像 $n$ を2回施すと元に戻るということを述べている。このことからも、 $n$ が符号を反転させるための写像として相応しい性質を持っていることが分かるだろう。

続いて式3であるが、これは和を取ってから符号を反転したものは、符号を反転してから和を取ったものと一致することを述べている。これは $S_d$ を加法について群と見なした時に、 $n$ が群準同型になっていることを示している。

最後に、式4は符号を反転した2つの整数の積が符号を反転する前の2つの整数の積に等しいことを示している。これにより、さまざまな符号の組み合わせでの掛け算をうまく定義できるようになる。

全単射性

符号を反転する写像であるならば、 $n$ は全単射であって欲しいが、果たしてそうなっているであろうか？以下で確かめてみよう。

単射性の証明

$\mathrm{Ker}(n)$ が自明であることを示す。任意の $x \in \mathrm{Ker}(n)$ について $n(x) = 0_b$ が成立する。これを変形すると以下のようになる。

$\displaystyle{ \begin{eqnarray} n(x) &=& 0_b \\ \overline{x} + 1_b &=& 0_b \\ \overline{x} + 1_b + \overline{0_b} &=& 0_b + \overline{0_b} \\ \overline{x} &=& \overline{0_b} \\ x &=& 0_b \end{eqnarray} }$

よって $\mathrm{Ker}(n) = \{0_b\}$ となる。

全射性の証明

$n(n(x)) = x$ より明らかである。

以上により、 $n$ は全単射である。 $n$ は群準同型でもあり、かつ $S_d$ を $S_d$ 自身に写すため、結局 $n$ は $S_d$ の群自己同型となる。

不動点

符号付き整数の特異な構造を理解するために、 $n$ の不動点について理解しておくことは重要である。どのような点が不動点になるか、具体的に計算で確かめてみよう。

$\displaystyle{ \begin{eqnarray} n(x) &=& x \\ n(x) + x &=& x + x \\ x + x &=& 0_b \end{eqnarray} }$

この条件を満たすビット列としては $0_b, 100...0_b$ の2つがある。後述するが、例えば1バイトの符号付き整数の場合、 $10000000_b$ は-128に対応する。これの符号を反転しようとしても、残念ながら符号は変わらず-128のままとなる。

これについても念のため実際のプログラムで確かめておこう。

サンプルコード：

#include <stdio.h>

int main()
{
    int a = (1 << 31);
    printf("a = %d, -a = %d\n", a, -a);
    return 0;
}

実行結果：

a = -2147483648, -a = -2147483648

考察の通り、符号を反転しても値が変わらないという結果になった。

$n$ は環自己同型か？

ここまで $n$ が $S_d$ の群自己同型であることを見た。しかし、 $S_d$ は環なのだから、環準同型にはならないのか？という疑問は当然湧いてくる。結論から言うと、 $d = 1$ の時に限り $n$ は環準同型になるが、それ以外の場合にはそうならない。

実際、環準同型であるためには $n(1_b) = 1_b$ となる必要があるが、 $1_b$ が $n$ の不動点になるのは $d = 1$ の時だけである。

ビット列と符号付き整数の対応

これまでの議論を元に、ビット列と符号付き整数の対応関係を以下に示す。

ビット列	符号付き整数	$n$ の不動点	備考
$000 \cdots 00_b$	0	○	加法の単位元
$000 \cdots 01_b$	1		乗法の単位元
$000 \cdots 10_b$	2
...	...
$011 \cdots 11_b$	$2^d - 1$
$100 \cdots 00_b$	$-2^d$	○
$100 \cdots 01_b$	$-2^d + 1$		$n(011 \cdots 11_b)$
...	...
$111 \cdots 10_b$	-2		$n(000 \cdots 10_b)$
$111 \cdots 11_b$	-1		$n(000 \cdots 01_b)$

0以上の整数は最上位ビットが0、負の整数は最上位ビットが1になっていることが分かる。これより、最上位ビットは符号ビットと呼ばれる。

結局、符号ビットが0の整数に対してビット反転して1を足したものを、その整数の符号を反転して得られる負の整数としているわけである。こんなよく分からない規則で負の数を作り出している割には、足し算・掛け算はビット列を符号無し整数とみなした時と同じ規則で行えるというのは、なんとも不思議な気持ちになる。しかし、それは全て写像 $n$ の性質に裏打ちされてのことなのである。