非常規進位 —— 以 -2 為底的按位計數系統

05-03

作為計算機相關從業人員，非 10 進位，特別是 2 / 8 / 16 進位應該都特別熟悉；不同進位之間的換算應該也爛熟於心，比如

$(1101)_2 = (15)_8 = (13)_{10} = (d)_{16}$

在本文中，將會介紹一個非常規進位 —— -2 進位。在實際系統中，可能並不實用，但如果作為一個開放性討論方向，-2 進位具有其自身獨特的優良性質 —— 可以直接表示負數

-2 進位的定義

我們知道，對於一個以 2 為底的 0 和 1 位串 $a_n a_{n-1}...a_2a_1a_0$ ，其與 10 進位之間的轉換為

$(a_n a_{n-1}...a_2a_1a_0)_{2} = 2^na_n + 2^{n-1}a_{n-1} + 2^2a_2 + 2a_1 + a_0$

類似的，如果有一個以 -2 為底的 0 和 1 位串 $a_n a_{n-1}...a_2a_1a_0$ ，那麼我們定義其含義如下

$(a_n a_{n-1}...a_2a_1a_0)_{-2} = (-2)^na_n + (-2)^{n-1}a_{n-1} + (-2)^2a_2 + (-2)a_1 + a_0$

比如

$(1101)_{-2} = (-2)^3 cdot 1 + (-2)^2 cdot 1 + (-2) cdot 0 + 1 = (-3)_{10}$

-2 進位的性質

使用 -2 進位，其無需類似正數進位那樣需要額外的處理（如 1-補碼或 2-補碼）即可表示負數
對於 -2 進位的 $n$ 位位串，其能表示 $2^n$ 個不同整數，且這些整數是連續的。更具體的，如果 $n$ 是偶數， $n$ 位位串能表示 $[frac{2 - 2^{n+1}}{3}, frac{2^n - 1}{3}]$ ；如果 $n$ 是奇數， $n$ 位位串能表示 $[frac{2 - 2^{n}}{3}, frac{2^{n+1} - 1}{3}]$
作為性質 2 的推廣；對於 -2 進位的 $n$ 位位串，如果位串的位數 $n$ 足夠，-2 進位可以表示所有整數且位串和整數為一一映射

對於性質 1，其顯而易見；對於性質 3，在這裡我們假設如果性質 2 成立，下面證明一部分 —— 性質 2 成立時，任意整數 $d$ 都能被某一個 -2 進位位串表示

假設性質 2 成立時，存在一個整數 $d$ 不能被任意 -2 進位位串表示。由於 $f(n) = frac{2 - 2^{n+1}}{3}$ 是一個嚴格遞減函數，且當 $n ightarrow +infty$ 時， $f(n) ightarrow -infty$ ，則必然存在 $n > n_0$ 使得 $f(n) < d$ ；類似的，可以證明對於 $g(n) = frac{2^n - 1}{3}$ ，必然存在 $n > n_1$ ，使得 $g(n) > d$ 。由性質 2 可得，若 $max(n_0, n_1)$ 為偶數，則 $n = max(n_0, n_1)$ 位位串必然可以表示 $d$ ，矛盾；若 $max(n_0, n_1)$ 為奇數，則 $n = max(n_0, n_1) + 1$ 位位串必然可以表示 $d$ ，矛盾，故任意整數 $d$ 必然可以被某一個 -2 進位位串表示

性質 3 的後一部分同樣使用反證法很容易證明，略；所以，現在只需要證明性質 2 即可，在嚴格證明之前，我們先來直觀感受下性質 2

-2 進位十進位 -2 進位十進位 0 0 1000 -8 1 1 1001 -7 10 -2 1010 -10 11 -1 1011 -9 100 4 1100 -4 101 5 1101 -3 110 2 1110 -6 111 3 1111 -5

由上表，當 $n = 1$ 時，表示範圍為 $[0, 1]$ ；當 $n = 2$ 時，表示範圍為 $[-2, 1]$ ；當 $n = 3$ 時，表示範圍為 $[-2, 5]$ ；當 $n = 4$ 時，表示範圍為 $[-10, 5]$ ；這裡有個特點，當 $n$ 遞增 1 時，表示範圍的邊界有一邊保持不動。現在，我們使用數學歸納法來證明性質 2

我們已經通過枚舉，證明了對於 $n = 1$ 時， $[frac{2 - 2^{1}}{3}, frac{2^{1+1} - 1}{3}] = [0, 1]$ 性質 2 成立；對於 $n = 2$ 時， $[frac{2 - 2^{3}}{3}, frac{2^2 - 1}{3}] = [-2, 1]$ 性質 2 同樣成立。假定當 $n = m$ 時，性質 2 成立。則對於 $n = m + 1$ ，位串 ${(a_{m} a_{m - 1}...a_2a_1a_0)_{-2}} = {(0a_{m - 1}...a_2a_1a_0)_{-2}} cup {(1 a_{m - 1}...a_2a_1a_0)_{-2}}$ ，其中 $(0a_{m - 1}...a_2a_1a_0)_{-2}$ 可以表示 $n = m$ 的所有整數； $(1 a_{m}...a_2a_1a_0)_{-2}$ 可以表示 $n = m$ 的所有整數加上 $(-2)^{m }$ 。如果 $m$ 是奇數， $(-2)^{m}$ 為負，則 $m + 1$ 位位串表示範圍為 $[frac{2 - 2^{m}}{3}, frac{2^{m+1} - 1}{3}] cup [frac{2 - 2^{m}}{3} - 2^{m} , frac{2^{m+1} - 1}{3} - 2^{m}] = [frac{2 - 2^{(m + 1) + 1}}{3}, frac{2^{m + 1} - 1}{3}]$ ；如果 $m$ 是偶數， $(-2)^{m}$ 為正，則 $m + 1$ 位位串表示範圍為 $[frac{2 - 2^{m+1}}{3}, frac{2^m - 1}{3}] cup [frac{2 - 2^{m+1}}{3} + 2^m, frac{2^m - 1}{3} + 2^m] = [frac{2 - 2^{m+1}}{3}, frac{2^{(m+1) + 1} - 1}{3}]$ 。性質 2 得證

10 進位到 -2 進位的轉換

既然已經知道任意整數都可以找到一個 -2 進位位串表示，那麼如果指定一個整數 $d$ ，它對應的 -2 進位位串是如何表示的？在描述這個轉換過程之前，我們先引入一個名詞『餘數非負式除法』。計算機整數除法的實現有很多種，比如 c++ / Java 中實現的是『向 0 取整式除法』。意思，c = a / b （a, b, c 都為整型），c 將向 0 取整，而餘數 d= a % b = a - b * c。如下

9 / 4 = 2 9 % 4 = 1-9 / 4 = -2 -9 % 4 = -1 9 / -4 = -2 9 % -4 = 1-9 / -4 = 2 -9 % -4 = -1

不同語言的整數除法 / 求余的規則不一樣，所以在使用其他語言時，要注意這一點。比如 Python2.7 是向下取整式除法

9 / 4 = 2 9 % 4 = 1-9 / 4 = -3 -9 % 4 = 3 9 / -4 = -3 9 % -4 = -3-9 / -4 = 2 -9 % -4 = -1

還有就是『餘數非負式除法』，顧名思義，在這種實現中，餘數必然為非負

9 / 4 = 2 9 % 4 = 1-9 / 4 = -3 -9 % 4 = 3 9 / -4 = -2 9 % -4 = 1-9 / -4 = 3 -9 % -4 = 3

在整數 $d$ 向 -2 進位轉換時，將使用『餘數非負式除法』讓整數 $d$ 反覆除以 -2，得到餘數 0 或者 1，直到商為 0。然後根據得到餘數的先後順序，從後到前依次排列即得對應的 -2 進位位串，如整數 -6

-6 / -2 = 3 -6 % -2 = 0 3 / -2 = -1 3 % -2 = 1-1 / -2 = 1 -1 % -2 = 1 1 / -2 = 0 1 % -2 = 1

即得 $(-6)_{10} = (1110)_{-2}$ ，證明可以從定義容易得知，略

-2 進位的運算

-2 進位雖然可以不加額外轉換即可表示負數，但其有一個很大的缺陷在於 -2 進位的運算相對正整數進位要複雜很多，這也是其不實用的主要原因之一。在文本中簡略的描述下 -2 進位的加減法

首先，從定義可以顯然得到，和正整數進位一樣，-2 進位加減法同樣可以按位來分別計算。有所不同的是，其按位計算的進位方式有所不同

因為

10 進位 -2 進位 0 0 1 1 -1 11 2 110

可得，在 -2 進位里的加法

1 + 1 = 110 0 + 1 = 1 0 + 0 = 0

按位計算時最多可能出現 2 個進位（1 + 1 = 110），其可能會引入無限向上進位，使用下面等式進行化簡

11 + 1 = 0

比如十進位數 -3 + 5

1101+ 101-------------------------- 1100+ 110 末位 1 + 1 進位+ 100-------------------------- 010 倒數第二位 0 + 1 = 1，其餘高位 11 + 1 = 0+ 100-------------------------- 110 即十進位數 +2

對於 -2 進位的減法

0 - 1 = 11 1 - 0 = 111 - 1 = 10

可見，在 -2 進位減法中不存在借位，同加法一樣只存在進位，比如 2 - 5 = 2 + (-5)

110+ 1111-------------------------- 110+ 11 將 1111 分為 1100 + 11+ 1100-------------------------- 01+ 1100-------------------------- 1101 即十進位數 -3

可以看到，-2 進位的加減法相對 +2 進位的加減法更為複雜。但如果形容 -2 進位的加減法只是更為複雜一點，那麼對於 -2 進位，除法的實現可能就稱得上極其複雜，在這裡就不多展開了

結語

非常規進位，除了類似 -2 進位這種負整數進位以外，還有以 $-1 + i$ 等虛數為底的按位計數系統，其將表達範圍擴展到虛數域。不過這些特殊進位，在一般工程實踐中很難見到，可能更多的只是出於興趣來研究。在下面的 wiki 鏈接和引文中，有相關的討論，同時在『演算法心得 —— 高效演算法的奧秘』一書中也有一章介紹了這些內容，有興趣的同學可以參考

Negative base - Wikipedia?

en.wikipedia.org

如有疏漏，懇請指正