はじめに
AtCoderの公式解説がしょっぱい問題を自分なりにわかりやすく解説してみようという記事です。
問題概要
整数 $N$ の $-2$ 進数表記を求めなさい。
ABC 105: C – Base -2 Number
解説
問題テキストにもありますが、 $N$ の $-2$ 進数表記を $S = S_kS_{k-1}\dots S_1S_0$ とすると、次が満たされます。
- $S_i$ は
1または0である - $N \neq 0$ ならば $S_k$ は
1である - $N = S_k(-2)^k + S_{k-1}(-2)^{k-1} + \cdots + S_1(-2)^1 + S_0(-2)^0$ が成り立つ
試しに、いくつかの $N$ について $-2$ 進数表記を求めてみると、次のようになります。
| $N$ | $S$ | $N$ | $S$ |
|---|---|---|---|
| 0 | 0 |
||
| 1 | 1 |
-1 | 11 |
| 2 | 110 |
-2 | 10 |
| 3 | 111 |
-3 | 1101 |
| 4 | 100 |
-4 | 1100 |
| 5 | 101 |
-5 | 1111 |
| 6 | 11010 |
-6 | 1110 |
| 7 | 11011 |
-7 | 1001 |
| 8 | 11000 |
-8 | 1000 |
| 9 | 11001 |
-9 | 1011 |
| 10 | 11110 |
-10 | 1010 |
| 11 | 11111 |
-11 | 110101 |
このくらいなら手計算で簡単に出せますが、大きな数になるとそうもいかないので、何らかのアルゴリズムを考える必要があります。
以下、各 $S_i$ を通常の2進数と同じように「ビット」と呼びます。
アルゴリズム
では、$N = -150$ に対する $S$ を求めてみましょう。
まず、$-150 = (-2)^7 + (-22)$ と分解します。このとき、$-150 = (-2)^5 + (-118)$ でもないし、$-150 = (-2)^9 + 362$ でもありません。
$N_1 = N - (-2)^k$ とおくと、
\sum_{0 \leq 2i+1 < k} (-2)^{2i+1} \leq N_1 \leq \sum_{0 \leq 2i < k} (-2)^{2i}
である必要があります。
いまの場合、$(-2)^7$ 未満のビットのみで表せる数は、最小で $(-2)^5 + (-2)^3 + (-2)^1 = -42$ 以上、最大で $(-2)^6 + (-2)^4 + (-2)^2 + (-2)^0 = 85$ 以下なので、$22$ はこの範囲内にあり適しています。
しかし、$(-2)^5$ 未満のビットのみで表せる数は、最小で $(-2)^3 + (-2)^1 = -9$ 以上、最大で $(-2)^4 + (-2)^2 + (-2)^0 = 21$ 以下なので、$-118$ を表すことができません。
また、$(-2)^9$ 未満のビットのみで表せる数は、最小で $(-2)^7 + (-2)^5 + (-2)^3 + (-2)^1 = -170$ 以上、最大で $(-2)^8 + (-2)^6 + (-2)^4 + (-2)^2 + (-2)^0 = 341$ 以下なので、やはり $362$ を表すことができません。
以下、同様に $-22 = (-2)^5 + 10$、$10 = (-2)^4 + (-6)$、$-6 = (-2)^3 + 2$ と分解できます。したがって、$N = -150$ に対する $-2$ 進数表記は $10111010$ であることがわかりました。
まとめると次のようになります。
- $(-2)^k$ のビットが立つかどうかを判定する。ビットが立つ条件は、$\sum_{0 \leq 2i+1 < k} (-2)^{2i+1} \leq N' \equiv N - (-2)^k \leq \sum_{0 \leq 2i < k} (-2)^{2i}$ が成り立つことである。
- ビットが立つ場合は $N := N - (-2)^k$ とする。$k$ を $1$ 減らして1.に戻る。
ループの開始条件は、$|N|$ を2進数で表した場合の最高ビットの2つ上から始めれば十分だと思います。もちろん $k = 31$ から始めてもよいでしょう。ループの終了条件は $k<0$ です。
実装例