マイナス2進数の考察

古くはビル・ゲイツの試験、最近だと #tcfm で話題になった「マイナス2進数」が興味深い。

導入

Answer 33 Count in base negative 2.

...

In general, any base works like a set of building blocks of differnt sizes. In base 10, the blocks come in sizes 1, 10, 100, 1,000, etc. In base 2, the blocks come in sizes 1, 2, 4, 8, 16, etc. Combining units in these standard sizes creates any desired number.

So what would base -2 notation be?

...

— "How Would You Move Mount Fuji?: Microsoft's Cult of the Puzzle - How the World's Smartest Companies Select the Most Creative Thinkers"

2進数は、一番右のビット(LSB)を2⁰、その次が2¹、その次が2²… と表現することだが、ここでのマイナス2進数とは「メカニカルに」2→-2に置き換えたものだ。すなわち、一番右のビット(LSB)を(-2)⁰、その次が(-2)¹、その次が(-2)²… と表現することだ。

マイナス2進数のLSBから0番目として桁を振っていったとしてマイナス2進数の各桁を $n_{k} \in \{0, 1\} (0 \leq k \leq L - 1)$ すなわち数値を $n_{L - 1} n_{L - 2} n_{L - 3} ... n_{1} n_{0}$ と表すとすると、10進数への変換式は

\sum_{k = 0}^{L - 1} n_{k} {(- 2)}^{k}

ちなみに4桁のマイナス2進数と10進数の関係は下記のようになる。

count base negative 2 in 4-bits
decimal	base negative 2
-10	1010
-9	1011
-8	1000
-7	1001
-6	1110
-5	1111
-4	1100
-3	1101
-2	0010
-1	0011
0	0000
1	0001
2	0110
3	0111
4	0100
5	0101

これの逆変換式を求めたい。

補題：ビット幅で表現できる数値

手計算すると感覚的に下記の通りビット幅拡張によって表現できる範囲が、正の方向と負の方向の交互に隙間なく広がることがわかる。

bit length vs range of "base negative 2"
bit length: L	minimal	MAXIMUM
1	0	1
2	-2	1
3	-2	5
4	-10	5

Lビット列のマイナス2進数で表現できる値の最大値と最小値は、手続き的に書くとそれぞれ下記の通り。

fn mbin_positive_max(l: u32) -> i32 {
    let mut val = 0;
    for i in 0..l {
        if i % 2 == 0 {
            val = val + pow2u32(i) as i32;
        }
    }
    val
}

fn mbin_negative_min(l: u32) -> i32 {
    let mut val = 0;
    for i in 0..l {
        if i % 2 == 1 {
            val = val - pow2u32(i) as i32;
        }
    }
    val
}

#[inline]
fn pow2u32(exp: u32) -> u32 {
    1 << exp
}

なお、等比級数の和であるのだから数式としては

\frac{4^{⌈\frac{L}{2}⌉} - 1}{3}, - \frac{2 (4^{⌊\frac{L}{2}⌋} - 1)}{3}

注意すべき点としては、 Lが奇数ならば、Lビットのときの最大値はL+1ビットの最大値と同じで Lビットのときの最小値はL-1ビットの最小値と同じである。また、Lが偶数ならば、Lビットのときの最大値はL-1ビットの最大値と同じで Lビットのときの最小値はL+1ビットの最小値と同じである。

実のところマイナス2進数では、上述の範囲内の数値は隙間なくすべて表現できる。 Lの数値が小さいときは手作業で確認できるとして、このルールが続くことを下記に示す。

Lが奇数のとき、L-1ビットからLビットに拡張したときに広がる数値の範囲の最小値は、最も左のビット(MSB)が1となる数値の値に、L-1ビットのときの最小値(これはLビットのときの最小値と同じであるが)を加算した値である。

2^{L - 1} - \frac{2 (4^{\frac{L - 1}{2}} - 1)}{3}

これを解くと

... = \frac{2^{L - 1} + 2}{3} = \frac{2^{L - 1} - 1}{3} + 1 = \frac{4^{\frac{L - 1}{2}} - 1}{3} + 1

であるから、L-1ビットのときの最大値(これはL-2ビットのときの最大値に同じ)に +1加算したものと等しい。

よって、Lが奇数のとき、L-1ビットのとき隙間なくすべて表現できるのならば、 Lビットのときも隙間なくすべて表現できる。

Lが偶数のとき(ただし0は除く)も同様に、L-1ビットからLビットに拡張したときに広がる数値の範囲の最大値は、

- 2^{L - 1} + \frac{4^{\frac{L}{2}} - 1}{3} = ... = - \frac{2 (4^{\frac{L}{2}} - 1)}{3} - 1

であり、L-1ビットのときの最小値(これはLビットのときの最小値に同じ)に -1したものと等しい。

よって、Lが偶数のとき、L-1ビットのとき隙間なくすべて表現できるのならば、 Lビットのときも隙間なくすべて表現できる。

したがってLが偶数であっても奇数であっても、帰納的に隙間なく表現できる、すなわちビット幅拡張によって表現できる範囲が隙間なく広がっていくことを示せた。

10進数→マイナス2進数変換アルゴリズム

既述の補題の考察より、(有界な数値であるならば、) MSB側からビットが立つか判定していけば良いことがわかる。

r=10進数の値
k=L-1,L-2,...,1,0について繰り返し:
1. kビットからk+1ビットで拡張される値の範囲内に属するならば、kビット目の値 $m_{k} = 1$ 。そうでなければ0
2. rから $m_{k} {(- 2)}^{k}$ を引く
おわり。変換された値は $n_{L - 1} n_{L - 2} n_{L - 3} ... n_{1} n_{0}$

オンライン変換サンプル(powered by WebAssembly)

仕様：オーバーフローを考慮していないので絶対値の大きな値だとエラーが出たり不正な値がでる。やろうと思えばなんとか対処できそうだが本題ではないので省いた。

10進数を入力
マイナス2進数計算結果

ソースは rust で書いた後、WebAssembly に変換している。変換前のソースコードは gist:cat-in-136/d0efb4879290b09c8cebb358632d8749 においてある。 test code も書いてあり（WebAssembly からは取り除かれている）、こちらは official release (WebAssembly 非対応) の rust でも動作する。

なお WebAssembly の仕様上、文字列の引き渡しに問題があるので整数(u32)を単なる bitstring を表現するものとして扱ってやり取りしている。