-2進法
通常、2進法では 2
0
の位, 2
1
の位, 2
2
の位...というように位取りをする。
-2進法では、代わりに -2 の冪を使う。
10進法や2進法と異なり、負の整数も符号を使わずに表せる。
-2進法で全整数が一意に表せることの説明
桁数を増やすごとに (-2)
□
が足され、 それまでに埋め尽くされた領域がスライドしてコピーされるので、 全ての整数が-2進法で一意に表せる。
n
(-2)
n-1
n 桁以下の数
1
1
0,1
2
-2
-2,-1
,0,1
3
4
-2,-1,0,1,
2,3,4,5
4
-8
-10,-9,-8,-7,-6,-5,-4,-3
,-2,-1,0,1,2,3,4,5
-2進法では、1, -2, 4, -8, ... という数列を位に使うが、
一般に
s
0
1, s
1
2, s
2
4, s
3
8 ... (s
i
∈{1,-1})
という数列で、正負どちらの項も無限個あれば、
全整数を一意に表せる (数列の部分集合と整数が1対1に対応する)。
先ほどのスライド・コピー論法で言える。
10進から-2進への変換
まず n の偶奇で1の位を決定する。
次に n を、偶数なら n/(-2) で、奇数なら (n-1)/(-2) で置き換える。
(つまり -2 で割り、正方向に切り上げ)
これを n が0になるまで繰り返す。
-2進
2進
10進
(-1+i) 進法
この場合は、複素整数 z を
z = Σa
n
(-1+i)
n
(a
n
∈{0,1})
の形式で表すことになる。
k
(-1+i)
k
桁数ごとに色分けしてプロット
出典: 「ハッカーのたのしみ」
TODO: 一意性、1+i進、アルゴリズム