補数についての覚書
正整数の$q$進表現と$q$進$n$桁の補数
正整数の$q$進表現
正整数$q \in \mathbb{Z}_{\geq 2}$を固定する．
任意の正整数$N \in \mathbb{Z}_{\geq 1}$に対して，非負整数$n \in \mathbb{Z}_{\geq 0}$と$a_{0},\ldots,a_{n} \in \{0,\ldots,q-1\}$であって
$$
N = a_{n}q^{n} + a_{n-1}q^{n-1} + \cdots + a_{1}q + a_{0},\ a_{n} \neq 0$$
が成り立つものがただ1組存在する．
存在
$$
q^{N} > q^{N} -1 = (q-1)(q^{N-1} + \cdots + 1) > \sum_{0}^{N-1} 1 = N$$
より$\{m \in \mathbb{Z}_{\geq 1} \mid N < q^{m}\} \neq \varnothing$であるから，
$$
n := \min \{m \in \mathbb{Z}_{\geq 1} \mid N < q^{m}\} - 1 \in \mathbb{Z}_{\geq 0}$$
が定まる．定義より
$$
q^{n} \leq N < q^{n+1}$$
が成り立つ．
各$i \in \{0,\ldots,n\}$に対して
$$
a_{i} = \left\lfloor \frac{N}{q^{i}} \right\rfloor - \left\lfloor \frac{N}{q^{i+1}}\right\rfloor q \in \mathbb{Z}$$
とおく．床函数について
$$
\forall x \in \mathbb{R},\ x-1 < \left\lfloor x \right\rfloor \leq x$$
が成り立つことに注意すると，
$$
-1 = \left( \frac{N}{q^{i}} - 1\right) - \frac{N}{q^{i+1}} q < a_{i} < \frac{N}{q^{i}} - \left(\frac{N}{q^{i+1}} -1 \right) q = q$$
すなわち$0 \leq a_{i} \leq q-1$が成り立つことがわかる．また，
$$
a_{n} = \left\lfloor \frac{N}{q^{n}}\right\rfloor - \left\lfloor \frac{N}{q^{n+1}} \right\rfloor q = \left\lfloor \frac{N}{q^{n}}\right\rfloor \geq 1$$
が成り立つ．
さらに，
\begin{align}
a_{n}q^{n} + \cdots + a_{0}
&= \sum_{0}^{n} a_{i}q^{i}\\
&= \sum_{0}^{n} \left\lfloor \frac{N}{q^{i}}\right\rfloor q^{i} - \left\lfloor \frac{N}{q^{i+1}}\right\rfloor q^{i+1}\\
&= \left\lfloor \frac{N}{q^{0}} \right\rfloor q^{0} - \left\lfloor \frac{N}{q^{n+1}}\right\rfloor q^{n+1}\\
&= N
\end{align}
が成り立つ．
一意性
$N = \sum_{0}^{n} a_{i}q^{i} = \sum_{0}^{m} b_{j}q^{j}$と2通りに表わせたとする．もし
$$
[n = m] \land [\forall i,\ a_{i} = b_{i}]$$
が成り立たないとすると，
$$
0 = \sum a_{i}q^{i} - \sum b_{j}q^{j} =: \sum_{0}^{\ell} d_{k} q^{k},\ d_{\ell} \neq 0,\ |d_{k}| \leq q-1$$
と書ける．ところがこのとき
$$
q^{\ell} \leq \left|d_{\ell}q^{\ell}\right| = \left|- \sum_{0}^{\ell -1} d_{k}q^{k}\right| \leq \sum_{0}^{\ell -1} (q-1)q^{k} = q^{\ell} -1 < q^{\ell}$$
となり不合理である．
各$a_{i}$の定義より次が成り立つ：
\begin{align}
N &= \left\lfloor \frac{N}{q}\right\rfloor \cdot q + a_{0},\ 0 \leq a_{0} < q\\
\left\lfloor \frac{N}{q}\right\rfloor &= \left\lfloor \frac{N}{q^{2}}\right\rfloor \cdot q + a_{1},\ 0 \leq a_{1} < q\\
& \vdots \\
\left\lfloor \frac{N}{q^{i}}\right\rfloor &= \left\lfloor \frac{N}{q^{i+1}}\right\rfloor \cdot q + a_{i},\ 0 \leq a_{i} < q\\
& \vdots \\
\left\lfloor \frac{N}{q^{n-1}}\right\rfloor &= \left\lfloor \frac{N}{q^{n}}\right\rfloor \cdot q + a_{n-1},\ 0 \leq a_{n-1} < q\\
\left\lfloor \frac{N}{q^{n}}\right\rfloor &= 0 \cdot q + a_{n},\ 0 < a_{n} < q
\end{align}
すなわち，$a_{0},\ldots,a_{n}$は，$N$を$q$で割り，その商を$q$で割り，その商を$q$で割り，と商が$0$になるまで繰り返したときの各段階の余りである．
正整数$N \in \mathbb{Z}_{\geq 1}$に対して，定理1により定まる非負整数を用いて
$$
N = {a_{n}a_{n-1} \cdots a_{1}a_{0}}_{(q)}$$
と書き表わしたとき，これを$N$の絶対$q$進表現といい，$n+1$をその絶対桁数という（ことにする）．
\begin{align}
19 &= 9 \cdot 2 + 1\\
9 &= 4 \cdot 2 + 1\\
4 &= 2 \cdot 2 + 0\\
2 &= 1 \cdot 2 + 0\\
1 &= 0 \cdot 2 + 1
\end{align}
より$19$の絶対$2$進表現は$19 = {10011}_{(2)}$となる．
$N = {a_{n}\cdots a_{0}}_{(q)}$を正整数$N$の絶対$q$進表現とする．このとき，任意の$m \geq n$に対して
$$
N = 0 \cdot q^{m} + \cdots + 0 \cdot q^{n+1} + a_{n}q^{n} + \cdots + a_{0}$$
が成り立つので，
$$
N = \underbrace{0 \cdots 0}_{m-n}\,{a_{n}\cdots a_{0}}_{(q)}$$
と書いて，これを$N$の相対$q$進表現といい，$m+1$をその相対桁数という（ことにする）．また，$0$は$0 = \underbrace{0 \cdots 0}_{m+1}\,_{(q)}$と表わす．
$q$進$n$桁の補数
相対桁数が$n$の正整数$N = {a_{n-1} \cdots a_{0}}_{(q)},\,0 \leq a_{i} \leq q-1,\,$に対して，
$$
\overline{a_{i}} = (q-1) - a_{i},\ n-1 \geq i \geq 0$$
とおくと，$0 \leq \overline{a_{i}} \leq q-1$であるから
$$
\overline{N} := \overline{a_{n-1}}q^{n-1} + \cdots + \overline{a_{0}} = {\overline{a_{n-1}}\cdots\overline{a_{0}}}_{(q)}$$
により相対桁数が$n$の非負整数$\overline{N}$が定まる．このとき，
\begin{align}
N + \overline{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{align}
が成り立つ．
相対桁数が$n$の正整数$N$に対して
$$
c(N) := \overline{N} + 1 = q^{n} -N$$
を$q$進$n$桁の$N$の補数という（ことにする）．
$N + c(N) = q^{n}$より
$$
-N \equiv c(N) \bmod{q^{n}}$$
が成り立つ．したがって$c(N)$は$\mathbb{Z}/q^{n}\mathbb{Z}$における$N$の反対元を与えている．
以下，相対桁数が$n$の正整数のことを単に“$n$桁の正整数”という．
$n$桁の正整数の補数はまた$n$桁の正整数である．
$N$を$n$桁の正整数とする．このとき
$$
N + c(N) = q^{n},\ 1 \leq N < q^{n}$$
より
$$
0 < c(N) = q^{n} - N \leq q^{n} - 1$$
が成り立つ．
正整数$n$に対して
$$
\mathbb{N}_{(q)}^{n} = \{N \in \mathbb{Z} \mid 1 \leq N \leq q^{n}-1\} = \{n\,\text{桁の正整数}\}$$
とおくと，補題2より写像
$$
c = c_{(q)}^{n} \colon \mathbb{N}_{(q)}^{n} \to \mathbb{N}_{(q)}^{n};\ N \mapsto q^{n} - N$$
が定まる．
補数を取る写像$c \colon \mathbb{N}_{(q)}^{n} \to \mathbb{N}_{(q)}^{n}$について，$c \circ c = \id$が成り立つ．
任意の$N \in \mathbb{N}_{(q)}^{n}$に対して
$$
c(c(N)) = q^{n} - c(N) = N$$
が成り立つ．
計算の工夫
引き算
$M \geq N$を$n$桁の正整数とする．このとき
$$
M - N = (M + c_{(q)}^{n}(N)) - q^{n}$$
が成り立つ．
\begin{align}
q^{n}
&= 1 \cdot q^{n} + 0 \cdot q^{n-1} + \cdots + 0 \cdot q + 0\\
&\leq q^{n} + (M - N)\\
&= M + c_{(q)}^{n}(N)\\
&\leq (q^{n}-1) + (q^{n}-1)\\
&= 1 \cdot q^{n} + (q-1) \cdot q^{n-1} + \cdots + (q-1) \cdot q + (q-2)
\end{align}
であるから，上の等式は「$n$桁の正整数同士の差$M-N$は，減数の補数を足してから（$+c_{(q)}^{n}(N)$）繰り上がりを無視すれば（$-q^{n}$）求められる」ことを意味する．
掛け算
$M,N \in \mathbb{Z}_{\geq 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 \geq 0$$
より
$$
c(M) + c(N) \leq 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{align}
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{align}
と書ける．
以下，$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{align}
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{align}
が成り立つ．すなわち，正整数$MN$の$2n$桁の相対$q$進表現は
$$
MN = {a_{n-1} \cdots a_{0}b_{n-1}\cdots b_{0}}_{(q)}$$
で与えられる．
$c(M) = 17,\,c(N) = 23$であるから，
- $L = 983 -23 = 977 - 17 = 960 > 0$
- $c(M)c(N) = 17 \times 23 = (20 -3)(20 +3) = 400 -9 = 391 < 10^{3}$
より
$$
983 \times 977 = 960391$$
と簡単に（暗算で？）計算できる．
整数の$2$進表現
以下，$q = 2$とする．また，整数$z,w \in \mathbb{Z}$に対して
$$
[z,w] = \{x \in \mathbb{Z} \mid z \leq x \leq w\}$$
とおく．
正整数の相対$2$進表現を用いて整数を表わすことを考える．
$2$進$n$桁の補数
正整数$N \in [1,2^{n}-1]$の相対$2$進表現が
$$
N = a_{n-1}\cdots a_{n-k}\,\underbrace{10 \cdots 0}_{n-k}\,_{(2)},\ 1 \leq k < n$$
ならば，その補数$c_{(2)}^{n}(N) \in [1,2^{n}-1]$の相対$2$進表現は
\begin{align}
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{align}
より
$$
c_{(2)}^{n}(N) = \overline{a_{n-1}}\cdots \overline{a_{n-k}}\,\underbrace{10\cdots 0}_{n-k}\,_{(2)}$$
で与えられる．
- $5 = 10\textcolor{red}{1}_{(2)} = 010\textcolor{red}{1}_{(2)}$
- $c_{(2)}^{3}(5) = 2^{3} -5 = 3 = 01\textcolor{red}{1}_{(2)}$
- $c_{(2)}^{4}(5) = 2^{4} -5 = 11 = 101\textcolor{red}{1}_{(2)}$
- $14 = 11\textcolor{red}{10}_{(2)} = 011\textcolor{red}{10}_{(2)}$
- $c_{(2)}^{4}(14) = 2^{4} -14 = 2 = 00\textcolor{red}{10}_{(2)}$
- $c_{(2)}^{5}(14) = 2^{5} - 14 = 18 = 100\textcolor{red}{10}_{(2)}$
整数の$2$進表現
$n \in \mathbb{Z}_{\geq 2}$とする．写像
$$
\delta = \delta_{(2)}^{n} \colon \{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}) = \textcolor{red}{-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{align}
\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{align}
より，$\delta$は（well-defined かつ）全単射である．したがって$[-2^{n-1},2^{n-1}-1]$に属する整数は$\beta_{(2)}^{n} := (\delta_{(2)}^{n})^{-1}$により$n$桁の相対$2$進表現を持つ．
$$
\xymatrix{
{} \ar@/_0.7pc/[d]_{\delta_{(2)}^{n}} & {[0,\,2^{n-1}-1]} \ar[d]_{\id} & {\{2^{n-1}\} \cup [2^{n-1}+1,\,2^{n}-1]} \ar[d]^{-c_{(2)}^{n}} & {} \\
{} & {[0,\,2^{n-1}-1]} & {\{-2^{n-1}\} \cup [-2^{n-1}+1,\,-1]} & {} \ar@/_0.7pc/[u]_{\beta_{(2)}^{n}}
}$$
とくに，図式
$$
\xymatrix{
{[1,2^{n-1}-1]} \ar@{<->}@/^1.5pc/[r]^{c_{(2)}^{n}} \ar@{<->}@/_1.5pc/[dr]_{(-1)\text{倍}} & {[2^{n-1}+1,2^{n}-1]} \\
{} & {[-2^{n-1}+1,-1]} \ar[u]_{\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}({0\,b_{n-2} \cdots b_{0}}_{(2)})$$
で与えられる．
- $\beta_{(2)}^{2}(-1) = c_{(2)}^{2}({01}_{(2)}) = {11}_{(2)}$
- $\beta_{(2)}^{3}(-1) = c_{(2)}^{3}({001}_{(2)}) = {111}_{(2)}$
- $\beta_{(2)}^{3}(3) = {011}_{(2)}$
- $\beta_{(2)}^{4}(3) = {0011}_{(2)}$
- $\beta_{(2)}^{4}(-5) = c_{(2)}^{4}({0101}_{(2)}) = {1011}_{(2)}$
- $\beta_{(2)}^{6}(-5) = c_{(2)}^{6}({000101}_{(2)}) = {111011}_{(2)}$
$2$進表現の延長と制限
$m,n \in \mathbb{Z}_{\geq 2},\ m > n,\,$とする．
整数$z \in [-2^{n-1},2^{n-1}-1]$の$n$桁の$2$進表現が
$$
\beta_{(2)}^{n}(z) = {a_{n-1}a_{n-2} \cdots a_{0}}_{(2)}$$
ならば，$m$桁の$2$進表現は
$$
\beta_{(2)}^{m}(z) = \underbrace{a_{n-1}\cdots a_{n-1}}_{m-n}\,{a_{n-1}a_{n-2}\cdots a_{0}}_{(2)}$$
で与えられる．
\begin{align}
&\quad\ \delta_{(2)}^{m}(\underbrace{a_{n-1}\cdots a_{n-1}}_{m-n}\,{a_{n-1}a_{n-2}\cdots a_{0}}_{(2)})\\
&= -a_{n-1}2^{m-1} + a_{n-1}2^{m-2} + \cdots + a_{n-1}2^{n-1} + a_{n-2}2^{n-2} + \cdots + a_{0}\\
&= a_{n-1}(-2^{m-1} + 2^{m-2} + \cdots + 2^{n-1}) + a_{n-2}2^{n-2} + \cdots + a_{0}\\
&= a_{n-1}(-2^{m-1} + 2^{m-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_{(2)}^{n}({a_{n-1}a_{n-2} \cdots a_{0}}_{(2)})\\
&= z
\end{align}
より，
$$
\beta_{(2)}^{m}(z) = \underbrace{a_{n-1}\cdots a_{n-1}}_{m-n}\,{a_{n-1}a_{n-2}\cdots a_{0}}_{(2)}$$
が成り立つ．
整数$z \in [-2^{m-1},2^{m-1}-1]$の$m$桁の$2$進表現を
$$
\beta_{(2)}^{m}(z) = {a_{m-1}a_{m-2}\cdots a_{n}a_{n-1}a_{n-2} \cdots a_{0}}_{(2)}$$
とする．このとき，次は同値である：
- $z \in [-2^{n-1},2^{n-1}-1]$;
- $a_{m-1} = a_{m-2} = \cdots = a_{n} = a_{n-1}$.
さらに，この同値な条件のもとで，整数$z$の$n$桁の$2$進表現は
$$
\beta_{(2)}^{n}(z) = {a_{n-1}a_{n-2}\cdots a_{0}}_{(2)}$$
で与えられる．
(i)$\implies$(ii)
整数$z \in [-2^{n-1},2^{n-1}-1]$の$n$桁の$2$進表現を
$$
\beta_{(2)}^{n}(z) = {b_{n-1}b_{n-2} \cdots b_{0}}_{(2)}$$
とおく．このとき補題4より
$$
\beta_{(2)}^{m}(z) = \underbrace{b_{n-1} \cdots b_{n-1}}_{m-n}\,{b_{n-1}b_{n-2} \cdots b_{0}}_{(2)}$$
であるから，
$$
\beta_{(2)}^{m}(z) = {a_{m-1}a_{m-2}\cdots a_{n}a_{n-1}a_{n-2} \cdots a_{0}}_{(2)}$$
と比較して
$$
a_{m-1} = a_{m-2} = \cdots = a_{n} = a_{n-1} = b_{n-1}$$
および
$$
a_{i} = b_{i},\ n-2 \geq i \geq 0$$
を得る．
(ii)$\implies$(i)
$w = \delta_{(2)}^{n}({a_{n-1}a_{n-2} \cdots a_{0}}_{(2)}) \in [-2^{n-1},2^{n-1}-1]$とおくと，補題4より
$$
\beta_{(2)}^{m}(w) = \underbrace{a_{n-1}\cdots a_{n-1}}_{m-n}\,{a_{n-1}a_{n-2}\cdots a_{0}}_{(2)} = \beta_{(2)}^{m}(z)$$
が成り立つので，$z = w \in [-2^{n-1},2^{n-1}-1]$を得る．
和の$2$進表現
整数$z,w \in [-2^{n-1},2^{n-1}-1]$について，$z + w \in [-2^{n-1},2^{n-1}-1]$が成り立つとする．このとき，非負整数$\beta_{(2)}^{n}(z) + \beta_{(2)}^{n}(w) \in [0,2^{n+1}-1]$の$n+1$桁の相対$2$進表現を
$$
\beta_{(2)}^{n}(z) + \beta_{(2)}^{n}(w) = {d_{n}d_{n-1}d_{n-2} \cdots d_{0}}_{(2)}$$
とすると，整数$z+w \in [-2^{n-1},2^{n-1}-1]$の$n$桁の$2$進表現は
$$
\beta_{(2)}^{n}(z +w) = {d_{n-1}d_{n-2} \cdots d_{0}}_{(2)}$$
で与えられる．
$M = \beta_{(2)}^{n}(z),\, N = \beta_{(2)}^{n}(w) \in [0,2^{n}-1]$とおく．このとき
$$
\delta(M) + \delta(N) = \begin{cases}
\delta(M + N) &, 0 \leq M + N \leq 2^{n}-1\\
\delta(M + N - 2^{n}) &, 2^{n} \leq M + N\ ({}\leq 2^{n} + 2^{n-1} + \cdots +1\ )
\end{cases}$$
が成り立つことを示せばよい．（ただし$\delta = \delta_{(2)}^{n}$である．）
$\delta(M),\delta(N) \geq 0$のとき
$\delta(M) = M,\ \delta(N) = N$より$M + N = \delta(M) + \delta(N) \in [0,2^{n-1}-1]$となるので
$$
\delta(M) + \delta(N) = M+N = \delta(M+N)$$
が成り立つ．
$\delta(M) \geq 0,\ \delta(N) < 0$のとき
$M \leq 2^{n-1}-1 < N$であるから
$$
\delta(M) + \delta(N) = M + (- c_{(2)}^{n}(N)) = M + (N - 2^{n}) = (M+N) - 2^{n}$$
が成り立つ．したがって，
- $2^{n-1} \leq M+N \leq 2^{n}-1$のとき
$$ \delta(M+N) = -c_{(2)}^{n}(M+N) = (M+N) - 2^{n} = \delta(M) + \delta(N)$$
が成り立つ． - $2^{n} \leq M+N$のとき，
$$ M+N \leq (2^{n-1}-1) + (2^{n}-1) < 2^{n-1} + 2^{n}$$
より$0 \leq M+N -2^{n} < 2^{n-1}$であるから
$$ \delta(M+N-2^{n}) = M+N-2^{n} = \delta(M) + \delta(N)$$
が成り立つ．
$\delta(M), \delta(N) < 0$のとき
$2^{n-1} \leq M,N$より$2^{n} \leq M +N$であり，
\begin{align}
-2^{n-1}
&\leq \delta(M) + \delta(N)\\
&= (-c_{(2)}^{n}(M)) + (-c_{(2)}^{n}(N))\\
&= (M -2^{n}) + (N - 2^{n})\\
&= (M+N -2^{n}) - 2^{n}
\end{align}
より
$$
2^{n-1} = 2^{n} -2^{n-1} \leq M+N - 2^{n}$$
となるので，
\begin{align}
\delta(M+N-2^{n})
&= -c_{(2)}^{n}(M+N-2^{n})\\
&= (M+N-2^{n}) - 2^{n}\\
&= \delta(M) + \delta(N)
\end{align}
が成り立つ．
整数$z,w \in [-2^{n-1},2^{n-1}-1]$の$n$桁の$2$進表現をそれぞれ
\begin{align}
\beta_{(2)}^{n}(z) &= {a_{n-1}a_{n-2} \cdots a_{0}}_{(2)},\\
\beta_{(2)}^{n}(w) &= {b_{n-1}b_{n-2} \cdots b_{0}}_{(2)}
\end{align}
とし，非負整数$\beta_{(2)}^{n}(z) + \beta_{(2)}^{n}(w) \in [0,2^{n+1}-1]$の$n+1$桁の相対$2$進表現を
$$
\beta_{(2)}^{n}(z) + \beta_{(2)}^{n}(w) = {d_{n}d_{n-1}d_{n-2} \cdots d_{0}}_{(2)}$$
とする．このとき次は同値である：
- $z + w \in [-2^{n-1},2^{n-1}-1]$;
- $[a_{n-1} \neq b_{n-1}] \lor [a_{n-1} = b_{n-1} = d_{n-1}]$
(i)$\implies$(ii)
$a_{n-1} = b_{n-1}$のとき，$z,w$の正負と$z+w$の正負は一致するので，命題6より$a_{n-1} = b_{n-1} = d_{n-1}$を得る．
(ii)$\implies$(i)
$\bullet\ a_{n-1} \neq b_{n-1}$のとき：
$z < 0 \leq w$としてよい．このとき
$$
-2^{n-1} \leq z + 0 \leq z + w < 0 + w < 2^{n-1}$$
が成り立つ．
$\bullet\ a_{n-1} = b_{n-1} = d_{n-1} = 0$のとき：
$z,w \geq 0$より$\beta_{(2)}^{n}(z) = z,\,\beta_{(2)}^{n}(w) = w$であるから，
$$
d_{n}2^{n} \leq {d_{n}0d_{n-2}\cdots d_{0}}_{(2)} = z + w < 2^{n-1} + 2^{n-1} = 2^{n}$$
より$d_{n} = 0$を得る．よって
$$
0 \leq z +w = {00d_{n-2} \cdots d_{0}}_{(2)} \leq 2^{n-1}-1$$
が成り立つ．
$\bullet\ a_{n-1} = b_{n-1} = d_{n-1} = 1$のとき：
$z,w < 0$であるから$-2^{n-1} \leq z +w$を示せばよい．まづ
\begin{align}
\beta_{(2)}^{n}(z) + \beta_{(2)}^{n}(w)
&= (2^{n-1} + a_{n-2}2^{n-2} + \cdots + a_{0}) + (2^{n-1} + b_{n-2}2^{n-2} + \cdots + b_{0})\\
&= 2^{n} + (a_{n-2}+b_{n-2})2^{n-2} + \cdots + (a_{0} + b_{0})\\
&= d_{n}2^{n} + 2^{n-1} + d_{n-2}2^{n-2} + \cdots + d_{0}
\end{align}
より$d_{n} =1$がわかるので，
$$
2^{n-1} + d_{n-2}2^{n-2} + \cdots + d_{0} = (a_{n-2} + b_{n-2}) 2^{n-2} + \cdots + (a_{0}+b_{0})$$
が成り立つ．
- 各$\ell \in [2,n]$に対して$a_{n-\ell} + b_{n-\ell} \in \{0,1,2\}$となることに注意する．
- $\{\ell \in [2,n] \mid a_{n-\ell} + b_{n-\ell} = 2\} = \varnothing$とすると，
\begin{align} 2^{n-1} &\leq 2^{n-1} + d_{n-2}2^{n-2} + \cdots + d_{0}\\ &= (a_{n-2} +b_{n-2})2^{n-2} + \cdots + (a_{0}+b_{0})\\ &\leq 2^{n-2} + \cdots + 1\\ &= 2^{n-1}-1 \end{align}
となり不合理である．したがって
$$ k := \min \{\ell \in [2,n] \mid a_{n-\ell} + b_{n-\ell} = 2\}$$
が定まる． - このとき，任意の$\ell \in [2,k-1]$に対して$a_{n-\ell} + b_{n-\ell} \in \{0,1\}$であるが，実は$a_{n-\ell} + b_{n-\ell} = 1$が成り立つ．
- 実際，$\exists k' \in \{\ell \in [2,k-1] \mid a_{n-\ell} + b_{n-\ell} = 0\} \neq \varnothing$とすると
\begin{align} 2^{n-1} &\leq 2^{n-1} + d_{n-2}2^{n-2} + \cdots + d_{0}\\ &= (a_{n-2} +b_{n-2})2^{n-2} + \cdots + (a_{n-k'+1}+b_{n-k'+1})2^{n-k'+1} + (a_{n-k'-1}+b_{n-k'-1})2^{n-k'-1} + \cdots + (a_{0}+b_{0})\\ &\leq 2^{n-2} + \cdots + 2^{n-k'+1} + 2 \cdot (2^{n-k'-1} + \cdots + 1)\\ &= 2^{n-2} + \cdots + 2^{n-k'+1} + 2 \cdot (2^{n-k'} - 1)\\ &= 2^{n-1} -2 \end{align}
となり不合理である．
- 実際，$\exists k' \in \{\ell \in [2,k-1] \mid a_{n-\ell} + b_{n-\ell} = 0\} \neq \varnothing$とすると
- よって
\begin{align} z +w &= (-2^{n-1} + a_{n-2}2^{n-2} + \cdots + a_{0}) + (-2^{n-1} + b_{n-2}2^{n-2} + \cdots + b_{0})\\ &\geq -2^{n} + (a_{n-2} + b_{n-2})2^{n-2} + \cdots + (a_{n-k+1} + b_{n-k+1})2^{n-k+1} + (a_{n-k} + b_{n-k})2^{n-k}\\ &= -2^{n} + 2^{n-2} + \cdots + 2^{n-k+1} + 2 \cdot 2^{n-k}\\ &= -2^{n} + 2^{n-1}\\ &= -2^{n-1} \end{align}
が成り立つ．
計算例：足し算
具体的な数値で命題6を確認してみる．
$(\pm 3) + (\pm 5) \in [-2^{3},2^{3}-1] = [-8,7]$の計算
- $\beta_{(2)}^{4}(3) + \beta_{(2)}^{4}(-5) = {0011}_{(2)} + {1011}_{(2)} = 0\,\textcolor{red}{1110}_{(2)}$
- $\beta_{(2)}^{4}(3 + (-5)) = \beta_{(2)}^{4}(-2) = c_{(2)}^{4}({0010}_{(2)}) = \textcolor{red}{1110}_{(2)}$
- $\beta_{(2)}^{4}(-3) + \beta_{(2)}^{4}(5) = {1101}_{(2)} + {0101}_{(2)} = 1\,\textcolor{red}{0010}_{(2)}$
- $\beta_{(2)}^{4}((-3) + 5) = \beta_{(2)}^{4}(2) = \textcolor{red}{0010}_{(2)}$
- $\beta_{(2)}^{4}(-3) + \beta_{(2)}^{4}(-5) = {1101}_{(2)} + {1011}_{(2)} = 1\,\textcolor{red}{1000}_{(2)}$
- $\beta_{(2)}^{4}((-3) +(-5)) = \beta_{(2)}^{4}(-8) = c_{(2)}^{4}({1000}_{(2)}) = \textcolor{red}{1000}_{(2)}$
$3+5 \in [-2^{4},2^{4}-1] \smallsetminus [-2^{3},2^{3}-1]$に注意する．
- $\beta_{(2)}^{4}(3) + \beta_{(2)}^{4}(5) = {0011}_{(2)} + {0101}_{(2)} = {1000}_{(2)} = \beta_{(2)}^{4}(-8)$
- $\beta_{(2)}^{5}(3) + \beta_{(2)}^{5}(5) = {00011}_{(2)} + {00101}_{(2)} = 0\,\textcolor{red}{01000}_{(2)}$
- $\beta_{(2)}^{5}(3+5) = \beta_{(2)}^{5}(8) = \textcolor{red}{01000}_{(2)}$
積の$2$進表現
整数$z,w \in [-2^{n-1},2^{n-1}-1]$について，$zw \in [-2^{n-1},2^{n-1}-1]$が成り立つとする．このとき，非負整数$\beta_{(2)}^{n}(z) \times \beta_{(2)}^{n}(w) \in [0,2^{2n}-1]$の$2n$桁の相対$2$進表現を
$$
\beta_{(2)}^{n}(z) \times \beta_{(2)}^{n}(w) = {d_{2n-1} \cdots d_{n}d_{n-1}d_{n-2} \cdots d_{0}}_{(2)}$$
とすると，整数$zw \in [-2^{n-1},2^{n-1}-1]$の$n$桁の$2$進表現は
$$
\beta_{(2)}^{n}(zw) = {d_{n-1}d_{n-2} \cdots d_{0}}_{(2)}$$
で与えられる．
$M = \beta_{(2)}^{n}(z),\, N = \beta_{(2)}^{n}(w) \in [0,2^{n}-1]$とおく．このとき
$$
\delta(M) \cdot \delta(N) = \delta({d_{n-1}d_{n-2} \cdots d_{0}}_{(2)})$$
が成り立つことを示せばよい．
$\delta(M), \delta(N) \geq 0$のとき
$\delta(M) = M,\ \delta(N) = N$より$MN = \delta(M) \cdot \delta(N) \in [0,2^{n-1}-1]$となる．したがって$MN$の$2n$桁の相対$2$進表現は
$$
MN = \underbrace{0 \cdots 0}_{n}\,{0\,d_{n-2} \cdots d_{0}}_{(2)}$$
となるので，
$$
\delta(M) \cdot \delta(N) = MN = \delta({d_{n-1}d_{n-2} \cdots d_{0}}_{(2)})$$
が成り立つ．
$\delta(M), \delta(N) < 0$のとき
$M,N \geq 2^{n-1}$であるが，
- $\delta(M),\,\delta(N) \in [-2^{n-1},-1]$
- $\delta(M) \cdot \delta(N) \in [1,2^{n-1}-1]$
- $\delta(2^{n-1}) = -2^{n-1}$
より，$M,N > 2^{n-1}$でなければならない．このとき$c(M), c(N) \in [1,2^{n-1}-1]$であり，
$$
c(M) \cdot c(N) = (-c(M)) \cdot (-c(N)) = \delta(M) \cdot \delta(N) \in [0,2^{n-1}-1]$$
となる．ところで
$$
L := M - c_{(2)}^{n}(N) = N - c_{(2)}^{n}(M) = (M + N) - 2^{n} > 0$$
とおくと，
$$
MN = L \cdot 2^{n} + c(M) \cdot c(N)$$
が成り立つので，
$$
c(M) \cdot c(N) = {d_{n-1}d_{n-2}\cdots d_{0}}_{(2)}$$
を得る．したがって
$$
\delta(M) \cdot \delta(N) = \delta({d_{n-1}d_{n-2}\cdots d_{0}}_{(2)})$$
が成り立つ．
$\delta(M) \geq 0,\ \delta(N) < 0$のとき
$M \leq 2^{n-1}-1 < N$である．まづ
$$
\delta(M) \cdot \delta(N) = M \cdot (-c(N)) = -2^{n-1}$$
の場合を考える．このとき$M = 2^{k},\, k \in [1,n-2],\,$と書けるので，
$$
N = c(c(N)) = c(2^{n-k-1}) = 2^{n} - 2^{n-k-1} = 2^{n-1} + \cdots + 2^{n-k} + 2^{n-k-1}$$
となる．したがって
$$
MN = 2^{n+k-1} + \cdots + 2^{n} + 2^{n-1}$$
となるので，
$$
\delta(M) \cdot \delta(N) = -2^{n-1} = \delta(1\,\underbrace{0 \cdots 0}_{n-1}\,_{(2)}) = \delta({d_{n-1}d_{n-2}\cdots d_{0}}_{(2)})$$
が成り立つ．
以下，$\delta(M) \cdot \delta(N) = - M \cdot c(N) \in [-2^{n-1}+1,-1]$とする．このとき$M, c(N) \in [1,2^{n-1}-1]$であり，
$$
M \cdot c(N) = -\delta(M) \cdot \delta(N) \in [1,2^{n-1}-1]$$
となるので，$M \cdot c(N) = {0\,b_{n-2}\cdots b_{0}}_{(2)}$とおくと，
$$
\delta(M) \cdot \delta(N) = - \delta({0\,b_{n-2}\cdots b_{0}}_{(2)})$$
と書ける．ここで
$$
D_{n} = d_{2n-1}2^{n-1} + \cdots + d_{n}$$
とおくと
$$
M \cdot 2^{n} = MN + M \cdot c(N) = (D_{n} \cdot 2^{n} + {d_{n-1}d_{n-2}\cdots d_{0}}_{(2)}) + {0\,b_{n-2} \cdots b_{0}}_{(2)}$$
より，
$$
0 < {d_{n-1}d_{n-2} \cdots d_{0}}_{(2)} + {0\,b_{n-2} \cdots b_{0}}_{(2)} = (M - D_{n})2^{n} \leq (2^{n}-1) + (2^{n} - 1) < 2 \cdot 2^{n}$$
となる．したがって$M - D_{n} = 1$，すなわち
$$
{d_{n-1}d_{n-2} \cdots d_{0}}_{(2)} + {0\,b_{n-2} \cdots b_{0}}_{(2)} = 2^{n}$$
が成り立つ．よって$d_{n-1} = 1$であり，
\begin{align}
\delta(M) \cdot \delta(N)
&= -\delta({0\,b_{n-2} \cdots b_{0}}_{(2)})\\
&= -(b_{n-2}2^{n-2} + \cdots + b_{0})\\
&= -2^{n} + (2^{n-1} + d_{n-2}2^{n-2} + \cdots + d_{0})\\
&= -2^{n-1} + d_{n-2}2^{n-2} + \cdots + d_{0}\\
&= \delta({d_{n-1}d_{n-2} \cdots d_{0}}_{(2)})
\end{align}
が成り立つ．
証明中の記号を用いると
\begin{align}
\delta({d_{n-1}d_{n-2} \cdots d_{0}}_{(2)})
&= -d_{n-1}2^{n-1} + d_{n-2}2^{n-2} + \cdots + d_{0}\\
&= MN - D_{n}2^{n} - 2d_{n-1}2^{n-1}\\
&= MN - (D_{n} + d_{n-1})2^{n}
\end{align}
と書ける．したがって，
- $z,w \geq 0$のとき，$d_{n-1} = 0$であり，
$$ 0 = D_{n} + d_{n-1}$$
が成り立つ． - $z,w < 0$のとき，$d_{n-1} = 0$であり，
$$ \beta_{(2)}^{n}(z) + \beta_{(2)}^{n}(w)\ \text{の$n+1$桁目を無視} = (M+N) - 2^{n} = L = D_{n} + d_{n-1}$$
が成り立つ． - $z \geq 0,\ w < 0$のとき，$d_{n-1} = 1$であり，
$$ \beta_{(2)}^{n}(z) = M = D_{n} + d_{n-1}$$
が成り立つ．
検算の役には立ちそう？
整数$z,w \in [-2^{n-1},2^{n-1}-1]$の$n$桁の$2$進表現をそれぞれ
\begin{align}
\beta_{(2)}^{n}(z) &= \underbrace{a \cdots a}_{k}\,{aa_{n-k-2} \cdots a_{0}}_{(2)},\\
\beta_{(2)}^{n}(w) &= \underbrace{b \cdots b}_{\ell}\,{bb_{n-\ell-2} \cdots b_{0}}_{(2)} \neq \underbrace{1 \cdots 1}_{\ell}\,{10 \cdots 0}_{(2)} = \beta_{(2)}^{n}(-2^{n-\ell-1})
\end{align}
とする．このとき，
$$
k +\ell \geq n-1 \implies zw \in [-2^{n-1},2^{n-1}-1]$$
が成り立つ．
$$
\xymatrix{
{{10\cdots 0}_{(2)}} & {\cdots} & {{1\cdots 10}_{(2)}} & {{1 \cdots 11}_{(2)}} & {{0 \cdots 00}_{(2)}} & {{0\cdots 01}_{(2)}} & {\cdots} & {{01 \cdots 1}_{(2)}}\\
{\bullet} \ar@{-}[rrrrrrr] & {} & {\bullet} & {\bullet} & {\bullet} & {\bullet} & {} & {\bullet}\\
{-2^{n-1}} & {\cdots} & {-2} & {-1} & {0} & {1} & {\cdots} & {2^{n-1}-1}\\
}$$
命題5より
$$
-2^{n-k-1} \leq z < 2^{n-k-1}$$
および
$$
-2^{n-\ell-1} < w < 2^{n-\ell-1}$$
が成り立つ．よって$k+\ell \geq n-1$のとき
$$
|zw| < 2^{2n-2- (k+\ell)} \leq 2^{n-1}$$
が成り立つ．
逆は成り立たない．実際
- $\beta_{(2)}^{6}(4) = {000100}_{(2)}$
- $\beta_{(2)}^{6}(7) = {000111}_{(2)}$
を考えると，$4 \cdot 7 = 28 \in [-2^{5},2^{5}-1] = [-32,31]$だが$k +\ell = 2 + 2 \not\geq 5 = n -1$である．
計算例：掛け算
具体的な数値で命題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)}$
- $\beta_{(2)}^{6}(3) \times \beta_{(2)}^{6}(7) = {000011}_{(2)} \times {000111}_{(2)} = \underbrace{000000}_{D_{6}}\,\textcolor{red}{010101}_{(2)}$
- $\beta_{(2)}^{6}(3 \times 7) = \beta_{(2)}^{6}(21) = \textcolor{red}{010101}_{(2)}$
- $\beta_{(2)}^{6}(-3) \times \beta_{(2)}^{6}(-7) = {111101}_{(2)} \times {111001}_{(2)} = \underbrace{110110}_{D_{6}}\,\textcolor{red}{010101}_{(2)}$
- $\beta_{(2)}^{6}(-3) + \beta_{(2)}^{6}(-7) = \textcolor{grey}{1}\,{110110}_{(2)}$
- $\beta_{(2)}^{6}((-3) \times (-7)) = \beta_{(2)}^{6}(21) = \textcolor{red}{010101}_{(2)}$
- $\beta_{(2)}^{6}(3) \times \beta_{(2)}^{6}(-7) = {000011}_{(2)} \times {111001}_{(2)} = \underbrace{000010}_{D_{6}}\,\textcolor{red}{101011}_{(2)}$
- $\beta_{(2)}^{6}(3 \times (-7)) = \beta_{(2)}^{6}(-21) = \textcolor{red}{101011}_{(2)}$
- $\beta_{(2)}^{6}(-3) \times \beta_{(2)}^{6}(7) = {111101}_{(2)} \times {000111}_{(2)} = \underbrace{000110}_{D_{6}}\,\textcolor{red}{101011}_{(2)}$
- $\beta_{(2)}^{6}((-3) \times 7) = \beta_{(2)}^{6}(-21) = \textcolor{red}{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)}$
- $\beta_{(2)}^{6}(6) \times \beta_{(2)}^{6}(5) = {000110}_{(2)} \times {000101}_{(2)} = \underbrace{000000}_{D_{6}}\,\textcolor{red}{011110}_{(2)}$
- $\beta_{(2)}^{6}(6 \times 5) = \beta_{(2)}^{6}(30) = \textcolor{red}{011110}_{(2)}$
- $\beta_{(2)}^{6}(-6) \times \beta_{(2)}^{6}(-5) = {111010}_{(2)} \times {111011}_{(2)} = \underbrace{110101}_{D_{6}}\,\textcolor{red}{011110}_{(2)}$
- $\beta_{(2)}^{6}(-6) + \beta_{(2)}^{6}(-5) = \textcolor{grey}{1}\,{110101}_{(2)}$
- $\beta_{(2)}^{6}((-6) \times (-5)) = \beta_{(2)}^{6}(30) = \textcolor{red}{011110}_{(2)}$
- $\beta_{(2)}^{6}(6) \times \beta_{(2)}^{6}(-5) = {000110}_{(2)} \times {111011}_{(2)} = \underbrace{000101}_{D_{6}}\,\textcolor{red}{100010}_{(2)}$
- $\beta_{(2)}^{6}(6 \times (-5)) = \beta_{(2)}^{6}(-30) = \textcolor{red}{100010}_{(2)}$
- $\beta_{(2)}^{6}(-6) \times \beta_{(2)}^{6}(5) = {111010}_{(2)} \times {000101}_{(2)} = \underbrace{000100}_{D_{6}}\,\textcolor{red}{100010}_{(2)}$
- $\beta_{(2)}^{6}((-6) \times 5) = \beta_{(2)}^{6}(-30) = \textcolor{red}{100010}_{(2)}$
$2$冪による乗除：算術シフト
正整数$N$に対して$N \cdot q^{\pm k}$の相対$q$進表現は$N$の相対$q$進表現の左右に$0$を加減することで得られる．同様のことを整数の$2$進表現について考える．
$z \in [-2^{n-1},2^{n-1}-1],\ k \in [1,n-1]$とし，整数$z$の$n$桁の$2$進表現を
$$
\beta_{(2)}^{n}(z) = {a_{n-1}a_{n-2} \cdots a_{0}}_{(2)}$$
とする．このとき次は同値である：
- $z \cdot 2^{k} \in [-2^{n-1},2^{n-1}-1]$;
- $a_{n-1} = a_{n-2} = \cdots = a_{n-k} = a_{n-k-1}$.
さらに，この同値な条件のもとで，整数$z \cdot 2^{k}$の$n$桁の$2$進表現は
$$
\beta_{(2)}^{n}(z \cdot 2^{k}) = a_{n-k-1}a_{n-k-2} \cdots a_{0}\,\underbrace{0 \cdots 0}_{k}\,_{(2)}$$
で与えられる．
命題5より
\begin{align}
z \cdot 2^{k} \in [-2^{n-1},2^{n-1}-1]
&\iff -2^{n-1} \leq z \cdot 2^{k} < 2^{n-1}\\
&\iff -2^{n-k-1} \leq z < 2^{n-k-1}\\
&\iff z \in [-2^{(n-k)-1},2^{(n-k)-1}-1]\\
&\iff a_{n-1} = a_{n-2} = \cdots = a_{n-k} = a_{n-k-1}
\end{align}
を得る．
以下，$z \cdot 2^{k} \in [-2^{n-1},2^{n-1}-1]$とする．
- $k = n-1$のとき
$$ \beta_{(2)}^{n}(z) = {aa \cdots a}_{(2)}$$
すなわち$z \in \{-1,0\}$であり，したがって
$$ \beta_{(2)}^{n}(z \cdot 2^{n-1}) = a\,\underbrace{0 \cdots 0}_{n-1}\,_{(2)}$$
が成り立つ． - $k < n-1$のとき，$\beta_{(2)}^{n}(2^{k}) = 2^{k}$より非負整数$\beta_{(2)}^{n}(z) \times \beta_{(2)}^{n}(2^{k})$の$2n$桁の相対$2$進表現は
$$ \beta_{(2)}^{n}(z) \times \beta_{(2)}^{n}(2^{k}) = \underbrace{0 \cdots 0}_{n-k}\,{a_{n-1}a_{n-2} \cdots a_{n-k}\,a_{n-k-1}a_{n-k-2} \cdots a_{0}}\,\underbrace{0 \cdots 0}_{k}\,_{(2)}$$
であるから，命題7より
$$ \beta_{(2)}^{n}(z \cdot 2^{k}) = a_{n-k-1}a_{n-k-2}\cdots a_{0}\,\underbrace{0 \cdots 0}_{k}\,_{(2)}$$
が成り立つ．
- $\beta_{(2)}^{8}(-10) = c_{(2)}^{8}({0000\,1010}_{(2)}) = \textcolor{red}{1111}\,{0110}_{(2)}$
- \begin{align} \delta_{(2)}^{8}(\textcolor{red}{111}{0\,110}\textcolor{orange}{0}_{(2)}) &= -c_{(2)}^{8}({1110\,1100}_{(2)})\\ &= - ({0001\,0100}_{(2)})\\ &= -20\\ &= (-10) \cdot 2^{1} \end{align}
- \begin{align} \delta_{(2)}^{8}(\textcolor{red}{11}{01\,10}\textcolor{orange}{00}_{(2)}) &= -c_{(2)}^{8}({1101\,1000}_{(2)})\\ &= - ({0010\,1000}_{(2)})\\ &= - 40\\ &= (-10) \cdot 2^{2} \end{align}
- \begin{align} \delta_{(2)}^{8}(\textcolor{red}{1}{011\,0}\textcolor{orange}{000}_{(2)}) &= -c_{(2)}^{8}({1011\,0000}_{(2)})\\ &= - ({0101\,0000}_{(2)})\\ &= -80\\ &= (-10) \cdot 2^{3} \end{align}
- \begin{align} \delta_{(2)}^{8}({0110}\,\textcolor{orange}{0000}_{(2)}) &= {0110\,0000}_{(2)}\\ &= 96 \neq (-10) \cdot 2^{4} \notin [-128,127] \end{align}
$z \in [-2^{n-1},2^{n-1}-1],\ k \in [1,n-1]$とし，整数$z$の$n$桁の$2$進表現を
$$
\beta_{(2)}^{n}(z) = {a_{n-1}a_{n-2} \cdots a_{0}}_{(2)}$$
とする．このとき次は同値である：
- $z \cdot 2^{-k} \in [-2^{n-1},2^{n-1}-1]$;
- $a_{k-1} = a_{k-2} = \cdots = a_{0} = 0$.
さらに，この同値な条件のもとで，整数$z \cdot 2^{-k}$の$n$桁の$2$進表現は
$$
\beta_{(2)}^{n}(z \cdot 2^{-k}) = \underbrace{a_{n-1} \cdots a_{n-1}}_{k}\,{a_{n-1}a_{n-2} \cdots a_{k}}_{(2)}$$
で与えられる．
(i)$\implies$(ii)
整数$w := z \cdot 2^{-k} \in [-2^{n-1},2^{n-1}-1]$の$n$桁の$2$進表現を
$$
\beta_{(2)}^{n}(w) = {b_{n-1}b_{n-2} \cdots b_{0}}_{(2)}$$
とする．このとき$w \cdot 2^{k} = z \in [-2^{n-1},2^{n-1}-1]$であるから，命題9より
$$
b_{n-1} = b_{n-2} = \cdots = b_{n-k} = b_{n-k-1}$$
であり，
$$
\beta_{(2)}^{n}(w \cdot 2^{k}) = b_{n-k-1}b_{n-k-2} \cdots b_{0}\,\underbrace{0 \cdots 0}_{k}\,_{(2)}$$
が成り立つ．これを
$$
\beta_{(2)}^{n}(z) = {a_{n-1}a_{n-2} \cdots a_{k}a_{k-1} \cdots a_{0}}_{(2)}$$
と比較して
\begin{cases}
b_{i} = a_{k+i} &, n-k-1 \geq i \geq 0\\
a_{j} = 0 &, k-1 \geq j \geq 0
\end{cases}
を得る．よって
$$
\beta_{(2)}^{n}(z \cdot 2^{-k}) = \beta_{(2)}^{n}(w) = \underbrace{a_{n-1} \cdots a_{n-1}}_{k}\,{a_{n-1}a_{n-2} \cdots a_{k}}_{(2)}$$
が成り立つ．
(ii)$\implies$(i)
仮定より
\begin{align}
z
&= \delta_{(2)}^{n}(a_{n-1}a_{n-2} \cdots a_{k}\,\underbrace{0 \cdots 0}_{k}\,_{(2)})\\
&= -a_{n-1}2^{n-1} + a_{n-2}2^{n-2} + \cdots + a_{k}2^{k}\\
&= (-a_{n-1}2^{n-k-1} + a_{n-2}2^{n-k-2} + \cdots + a_{k}) \cdot 2^{k}
\end{align}
が成り立つので，
\begin{align}
z \cdot 2^{-k}
&= -a_{n-1}2^{n-k-1} + a_{n-2}2^{n-k-2} + \cdots + a_{k}\\
&= \delta_{(2)}^{n-k}({a_{n-1}a_{n-2} \cdots a_{k}}_{(2)}) \in [-2^{n-k-1},2^{n-k-1}-1] \subset [-2^{n-1},2^{n-1}-1]
\end{align}
が成り立つ．
- $\beta_{(2)}^{8}(-48) = c_{(2)}^{8}({0011\,0000}_{(2)}) = {1101}\,\textcolor{red}{0000}_{(2)}$
- \begin{align} \delta_{(2)}^{8}(\textcolor{orange}{1}110\,1\textcolor{red}{000}_{(2)}) &= - c_{(2)}^{8}({1110\,1000}_{(2)})\\ &= - ({0001\,1000}_{(2)})\\ &= -24\\ &= (-48) \cdot 2^{-1} \end{align}
- \begin{align} \delta_{(2)}^{8}(\textcolor{orange}{11}11\,01\textcolor{red}{00}_{(2)}) &= -c_{(2)}^{8}({1111\,0100}_{(2)})\\ &= - ({0000\,1100}_{(2)})\\ &= -12\\ &= (-48) \cdot 2^{-2} \end{align}
- \begin{align} \delta_{(2)}^{8}(\textcolor{orange}{111}1\,101\textcolor{red}{0}_{(2)}) &= -c_{(2)}^{8}({1111\,1010}_{(2)})\\ &= - ({0000\,0110}_{(2)})\\ &= -6\\ &= (-48) \cdot 2^{-3} \end{align}
- \begin{align} \delta_{(2)}^{8}(\textcolor{orange}{1111}{\,1101}_{(2)}) &= -c_{(2)}^{8}({1111\,1101}_{(2)})\\ &= - ({0000\,0011}_{(2)})\\ &= -3\\ &= (-48) \cdot 2^{-4} \end{align}
- \begin{align} \delta_{(2)}^{8}(\textcolor{orange}{1111\,1}{110}_{(2)}) &= - c_{(2)}^{8}({1111\,1110}_{(2)})\\ &= - ({0000\,0010}_{(2)})\\ &= -2 \neq (-48) \cdot 2^{-5} \notin [-128,127] \end{align}
