查看原题点 这里 。

这道题说到底还是用短除法递推求解。只是基数从整数变成了负数，所以相应的过程有细微的变化。

p.s. 短除法的原理可以看之前写的 进制转换的原理 。

负基数的短除法

过程与原来的短除法相似，这次以 -2 为基数举例。

设原来的十进制数为 n，转换后的 -2 进制数为 abcd（当然结果不一定是 4 位数，只是举个例子）。

现在已知 x，求 abcd，那么写出等式：

(abcd)−2=(n)10 $$(abcd)_{-2}=(n)_{10}$$

将左边转换为 10 进制，得到：

a×(−2)3+b×(−2)2+c×(−2)1+d×(−2)0=n $$a/times (-2)^3+b/times (-2)^2+c/times (-2)^1+d/times (-2)^0=n$$

除了最后一项 d 外，前几项都有公因式 -2，于是因式分解：

−2×(a×(−2)2+b×(−2)1+c)+d=n $$-2/times(a/times(-2)^2+b/times(-2)^1+c)+d= n$$

简便起见，将 a×(−2)2+b×(−2)1+c$a/times(-2)^2+b/times(-2)^1+c$ 简写为 k，于是等式变成：

−2k+d=n $$-2k+d=n$$

如果把 n 看成被除数，-2 看成除数，k 看成商，d 看成余数，那么等式就可以写成：

n÷(−2)=k…d $$n/div(-2)=k/ldots d$$

至此所有的步骤与正基数的短除法相同。下面就是本题最有趣的部分。

我们都知道余数和被除数的符号是相同的。

当 n 大于等于 0 时，处理方式还是和原来一样的。但是如果 n 小于 0 的话，那么 d 也会小于 0，但是我们知道 d 一定是在 [0, 2) 范围内的正整数，所以就需要对等式进行一些变换，使得余数大于等于 0：

n÷(−2)=k+1…d+2 $$n/div(-2)=k+1/ldots d+2$$

也就是说，把商加一，余数再减去一个除数，等式还是成立的。因为余数的绝对值一定是小于除数的绝对值，因此减去一个除数（相当于加上除数的绝对值）就能令余数非负，此时就能继续像以前一样计算了。

总结一下就是：还是用短除法，只是当余数小于 0 时，把商加一，把余数减去除数（即基数）使之为正，并保持等式成立，然后就直接像往常一样计算就行了。

代码