補数についての覚書

正整数の$q$進表現と$q$進$n$桁の補数

正整数の$q$進表現

正整数$q\in {\mathbb{Z}}_{\ge 2}$を固定する．

$q$進$n$桁の補数

相対桁数が$n$の正整数$N={a_{n-1}\cdots a_0}_{(q)},0\le a_i\le q-1,$に対して，
$$\overline{a_i}=(q-1)-a_i,n-1\ge i\ge 0$$
とおくと，$0\le \overline{a_i}\le q-1$であるから
$$\bar{N}:=\overline{a_{n-1}}{q}^{n-1}+\cdots +\overline{a_0}={\overline{a_{n-1}}\cdots \overline{a_0}}_{(q)}$$
により相対桁数が$n$の非負整数$\bar{N}$が定まる．このとき，
$$\begin{array}{rl}N+\bar{N}& =(a_{n-1}+\overline{a_{n-1}})q^{n-1}+\cdots +(a_0+\overline{a_0})\\ & =(q-1)q^{n-1}+\cdots +(q-1)\\ & =q^n-1\end{array}$$
が成り立つ．

以下，相対桁数が$n$の正整数のことを単に“$n$桁の正整数”という．

正整数$n$に対して
$${\mathbb{N}}_{(q)}^n=\{N\in \mathbb{Z}\mid 1\le N\le q^n-1\}=\{n\text{桁の正整数}\}$$
とおくと，補題2より写像
$$c=c_{(q)}^n:{\mathbb{N}}_{(q)}^n\to {\mathbb{N}}_{(q)}^n;N\mapsto q^n-N$$
が定まる．

計算の工夫

引き算

$M\ge N$を$n$桁の正整数とする．このとき
$$M-N=(M+c_{(q)}^n(N))-q^n$$
が成り立つ．
$$\begin{array}{rl}{q}^n& =1\cdot q^n+0\cdot q^{n-1}+\cdots +0\cdot q+0\\ & \le q^n+(M-N)\\ & =M+c_{(q)}^n(N)\\ & \le (q^n-1)+(q^n-1)\\ & =1\cdot q^n+(q-1)\cdot q^{n-1}+\cdots +(q-1)\cdot q+(q-2)\end{array}$$
であるから，上の等式は「$n$桁の正整数同士の差$M-N$は，減数の補数を足してから（$+c_{(q)}^n(N)$）繰り上がりを無視すれば（$-q^n$）求められる」ことを意味する．

掛け算

$M,N\in {\mathbb{Z}}_{\ge 2}$を$n$桁の正整数とする．それぞれの補数について，$1\in \{c(M),c(N)\}$のときは$c(M)c(N)<q^n$および
$$c(M)+c(N)<1+(q^n-1)=q^n$$
が，$c(M),c(N)>1$のときは
$$c(M)c(N)-(c(M)+c(N))=(c(M)-1)(c(N)-1)-1\ge 0$$
より
$$c(M)+c(N)\le c(M)c(N)$$
が成り立つ．また，
$$M+c(M)=q^n=N+c(N)$$
より，整数
$$L:=M-c(N)=N-c(M)=q^n-(c(M)+c(N))=(M+N)-q^n\in \mathbb{Z}$$
が定まる．したがって
$$\begin{array}{rl}MN& =(q^n-c(M))\cdot (q^n-c(N))\\ & =(q^n-c(M)-c(N))q^n+c(M)c(N)\\ & =L\cdot q^n+c(M)c(N)\end{array}$$
と書ける．

以下，$c(M)c(N)<q^n$が成り立つ，すなわち$c(M)c(N)$の桁が増えないと仮定する．このとき$L>0$であり，正整数$L,c(M)c(N)$の$n$桁の相対$q$進表現をそれぞれ

• $L={a_{n-1}\cdots a_0}_{(q)}$
• $c(M)c(N)={b_{n-1}\cdots b_0}_{(q)}$

とすると，
$$\begin{array}{rl}MN& =(a_{n-1}{q}^{n-1}+\cdots +a_0)\cdot q^n+(b_{n-1}{q}^{n-1}+\cdots +b_0)\\ & =a_{n-1}{q}^{2n-1}+\cdots +a_0{q}^n+b_{n-1}{q}^{n-1}+\cdots +b_0\end{array}$$
が成り立つ．すなわち，正整数$MN$の$2n$桁の相対$q$進表現は
$$MN={a_{n-1}\cdots a_0{b}_{n-1}\cdots b_0}_{(q)}$$
で与えられる．

整数の$2$進表現

以下，$q=2$とする．また，整数$z,w\in \mathbb{Z}$に対して
$$[z,w]=\{x\in \mathbb{Z}\mid z\le x\le w\}$$
とおく．

正整数の相対$2$進表現を用いて整数を表わすことを考える．

$2$進$n$桁の補数

正整数$N\in [1,2^n-1]$の相対$2$進表現が
$$N=a_{n-1}\cdots a_{n-k}\underset{n-k}{\underbrace{10\cdots 0}}{}_{(2)},1\le k<n$$
ならば，その補数$c_{(2)}^n(N)\in [1,2^n-1]$の相対$2$進表現は
$$\begin{array}{rl}{c}_{(2)}^n(N)& =2^n-(a_{n-1}{2}^{n-1}+\cdots +a_{n-k}{2}^{n-k}+2^{n-k-1})\\ & =(2^n-2^{n-k-1})-(a_{n-1}{2}^{n-1}+\cdots +a_{n-k}{2}^{n-k})\\ & =(2^{n-1}+\cdots +2^{n-k-1})-(a_{n-1}{2}^{n-1}+\cdots +a_{n-k}{2}^{n-k})\\ & =(1-a_{n-1})2^{n-1}+\cdots +(1-a_{n-k})2^{n-k}+2^{n-k-1}\\ & =\overline{a_{n-1}}\cdot 2^{n-1}+\cdots +\overline{a_{n-k}}\cdot 2^{n-k}+2^{n-k-1}\end{array}$$
より
$$c_{(2)}^n(N)=\overline{a_{n-1}}\cdots \overline{a_{n-k}}\underset{n-k}{\underbrace{10\cdots 0}}{}_{(2)}$$
で与えられる．

整数の$2$進表現

$n\in {\mathbb{Z}}_{\ge 2}$とする．写像
$$\delta ={\delta }_{(2)}^n:\{0\}\cup {\mathbb{N}}_{(2)}^n=[0,2^n-1]\to [-2^{n-1},2^{n-1}-1]$$
を
$$\delta (a_{n-1}{2}^{n-1}+a_{n-2}{2}^{n-2}+\cdots +a_0)=-a_{n-1}{2}^{n-1}+a_{n-2}{2}^{n-2}+\cdots +a_0$$
で定める．
$$\delta (0\cdot 2^{n-1}+a_{n-2}{2}^{n-2}+\cdots +a_0)=a_{n-2}{2}^{n-2}+\cdots +a_0\in [0,2^{n-1}-1]$$
および
$$\begin{array}{rl}\delta (1\cdot 2^{n-1}+a_{n-2}{2}^{n-2}+\cdots +a_0)& =-2^{n-1}+a_{n-2}{2}^{n-2}+\cdots +a_0\in [-2^{n-1},-1]\\ & =(2^{n-1}+a_{n-2}{2}^{n-2}+\cdots +a_0)-2^n\\ & =-c_{(2)}^n(1\cdot 2^{n-1}+a_{n-2}{2}^{n-2}+\cdots +a_0)\end{array}$$
より，$\delta$は（well-defined かつ）全単射である．したがって$[-2^{n-1},2^{n-1}-1]$に属する整数は${\beta }_{(2)}^n:=({\delta }_{(2)}^n{)}^{-1}$により$n$桁の相対$2$進表現を持つ．
$${\delta }_{(2)}^n[0,2^{n-1}-1]\mathrm{id}\{2^{n-1}\}\cup [2^{n-1}+1,2^n-1]-c_{(2)}^n[0,2^{n-1}-1]\{-2^{n-1}\}\cup [-2^{n-1}+1,-1]{\beta }_{(2)}^n$$
とくに，図式
$$[1,2^{n-1}-1]c_{(2)}^n(-1)\text{倍}[2^{n-1}+1,2^n-1][-2^{n-1}+1,-1]{\beta }_{(2)}^n$$
の可換性より次がわかる：$n-1$桁の正整数$N={b_{n-2}\cdots b_0}_{(2)}\in [1,2^{n-1}-1]$に対して，負整数$-N\in [-2^{n-1}+1,-1]$の$2$進表現は
$$c_{(2)}^n({0b_{n-2}\cdots b_0}_{(2)})$$
で与えられる．

$2$進表現の延長と制限

$m,n\in {\mathbb{Z}}_{\ge 2},m>n,$とする．

和の$2$進表現

計算例：足し算

具体的な数値で命題6を確認してみる．

$(\pm 3)+(\pm 5)\in [-2^3,2^3-1]=[-8,7]$の計算

積の$2$進表現

計算例：掛け算

具体的な数値で命題7を確認してみる．

$(\pm 3)\times (\pm 7)=\pm 21\in [-2^5,2^5-1]=[-32,31]$の計算

それぞれの整数の$2$進表現は以下のようになる：

• ${\beta }_{(2)}^6(3)={000011}_{(2)}$
• ${\beta }_{(2)}^6(-3)=c_{(2)}^6({000011}_{(2)})={111101}_{(2)}$
• ${\beta }_{(2)}^6(7)={000111}_{(2)}$
• ${\beta }_{(2)}^6(-7)=c_{(2)}^6({000111}_{(2)})={111001}_{(2)}$
• ${\beta }_{(2)}^6(21)={010101}_{(2)}$
• ${\beta }_{(2)}^6(-21)=c_{(2)}^6({010101}_{(2)})={101011}_{(2)}$

$(\pm 6)\times (\pm 5)=\pm 30\in [-2^5,2^5-1]=[-32,31]$の計算

それぞれの整数の$2$進表現は以下のようになる：

• ${\beta }_{(2)}^6(6)={000110}_{(2)}$
• ${\beta }_{(2)}^6(-6)=c_{(2)}^6({000110}_{(2)})={111010}_{(2)}$
• ${\beta }_{(2)}^6(5)={000101}_{(2)}$
• ${\beta }_{(2)}^6(-5)=c_{(2)}^6({000101}_{(2)})={111011}_{(2)}$
• ${\beta }_{(2)}^6(30)={011110}_{(2)}$
• ${\beta }_{(2)}^6(-30)=c_{(2)}^6({011110}_{(2)})={100010}_{(2)}$

$2$冪による乗除：算術シフト

正整数$N$に対して$N\cdot q^{\pm k}$の相対$q$進表現は$N$の相対$q$進表現の左右に$0$を加減することで得られる．同様のことを整数の$2$進表現について考える．