任意进制数的补码

关于任意进制数的补码问题，我主要是用来写任意进制的高精度运算的，自我感觉用处不是特别大，只是不用再单写一个高精度的减法了——减去一个数等于加上对应的负数的补码，这样可以解决很多麻烦的问题，不过现在网上已经有很多现成的高精度算法的模板了，把这个任意进制的补码问题写在这里，只是觉着有意思而已，而且也是为数不多的有些原创性的工作。 至于想到任意进制数的补码的原因，还要说到前段时间看一本书，给出了一段关于二进制加法的伪代码，非常短，不由想到了以前写的十进制的高精度算法的代码，突然发现这个原来可以推广到任意进制。这是一段挺经典的代码了，把伪代码在这里写一下。

两个加数进制数为base，分别为：(anan-1…a2a1)base，(bnbn-1…b2b1)base ，加得的数存到s中，则：

c ← 0
for i ← 1 to n
	temp ← [(ai+bi+c)/base]
	si ← ai+bi+c-temp*base
c ← temp

然后又看见了一个关于二进制乘法的算法，是一个分治算法，将两个n位的乘数分别拆分为高n/2位和低n/2位，我们知道对于进制数为base的数来说，将一个数左移t位就是乘以baset，那么我们可以推出以下的公式：

若A = (anan-1…a2a1)base， B = (bnbn-1…b2b1)base ，A1 = (anan-1…an/2+1)base，A0 = (an/2an/2-1…a1)base，B1 = (bnbn-1…bn/2+1)base，B0 = (bn/2bn/2-1…b1)base

则A*B = (basen/2*A1+A0)*(basen/2*B1+B0) = A1B1*basen+((A1-B1)(B0-A0)+A1B1+A0B0)*basen/2+A0B0

这样递归来算，在程序中需要调用三次乘法函数就可以了，假设这个算法的时间复杂度是T(n)，那么当n=1时，T(n)=O(1)，否则，T(n)=3T(n/2)+O(n)。用我们学过的可以解出来这个递归式的时间复杂度是T(n)=O(nlog3)=O(n1.585)。比普通高精度乘法算法的O(n2)要快一些。

由于看见了上面的两个算法，所以很想自己写一个任意进制的高精度算法，在写的过程中，出现了很多挺麻烦的问题，比如正数加负数什么的，需要一些判断，和我所想象的比较精简的代码不相符，于是突发奇想，觉得要是任意进制数都可以用补码来表示，那么代码会精简很多。但是当时脑子已经有点不好使了，没有细想，后来偶然和一个朋友提及此事，他对此也很感兴趣，于是我们两个花了两三个晚上的时间把任意进制的补码问题给研究了以下，下面就把成果说以下。因为水平实在有限，难免有不对之处，希望大家能够指正。

要考虑任意进制数的补码，我们可以从补码的来源来考虑。我们知道，一个钟表，如果指针在12点的位置，若想将它拨到三点的位置，既可以向前拨三个格，又可以向后拨九个格。可以认为这个钟表是一个十二进制的表示，-3的“补码”可以说是9。那么我们把它推广到我们比较熟悉的十进制，若是两个一位数相加，我们可以把它想想成一个有十个格的表盘，若是两位数，则可把它想象成一个有一百个格的表盘。这样一来，若是一位数，它的补码可以表示为10减去这个数，两位数的可以表示为100减去这个数，那么对于十进制数来说，一个任意负数的补码就是每位用9减去它，最后再加一，现在想想二进制的补码所谓的按位取反再加一，就是这个道理了。若是把这个规律推广到base进制，那么一个负数的补码就是按位用base减去它，然后再加一。

但是这样一来就会有一个问题，比如在十进制中，-3的补码是7，但是7的补码也是7，给定一个补码7,我们不知道这个数到底是-3还是7。这里我们可以借鉴一下二进制补码的写法，在前面增加补全符号位，若是base进制，负数的符号位就是base-1，正数的符号位是0。这样直接按位取反加一就可以得到一个数的补码了。

用我们熟悉的十进制数来举个例子，比如我们要算一下9-12，假设用三个单位的空间来存储数，那么9的补码就是009，-12的补码就是988，9-12用补码来算就是009+988=1997，其中1溢出了，结果就是993，按位取反加一得原数是-3，和正确结果是一致的。

我们再举一个例子，可以从这个例子看出来，取几个有效的存储空间是比较有讲究的。我们来考虑一下-99-99，若是取三位，那么用补码来算就是901+901=1802，那么结果溢出就错误了，若是用四位，用补码来算就是9901+9901=19802，1溢出之后就是9802，那么原数就是-198，是正确的结果。

我们很容易看出来，对于加法来说，取的位数是越多越好的，但是太多了未免浪费空间。可以知道两个数相加，相加的结果最多比其中的任何一个数大一位，再加上一个符号位，所以两个n位的数相加，只要用n+2个单位的空间存储就可以了。

乘法和加法是类似的，只是所取的有效位不一样而已，对于乘法我们可以知道结果的位数最多不会比两个数的位数的和大一位，所以如果两个数分别为n1和n2位的话，那么取n1+n2+2位就可以了。

举个例子来算一下-99×-99，取6个有效位，用补码来算就是999901×999901=999802009801，取6个有效位之后是009801，原数就是9801。和正确结果是一致的。

下面简单总结一下任意进制数补码的一些规则：

对于任意的base进制数，

1. 取补：正数的补码是它本身，负数的补码是按位用base减然后再加一。若原来的数有n位，则补码有效的位数是到n+1（其中第n+1位是符号位）。
2. 有效位：如果一个数的补码原本是x位，若要取有效位y(>x)，那么若该数是正数，则在x+1至y之间补0，否则补base-1。
3. 加法：一个a位数和b(<=a)位数相加，取有效位为a+2。
4. 乘法：一个a位数和b位数相加，有效位取a+b+2。

这样一来，我们已经把任意进这数的最简单的补码的规则给总结出来了。其中会有一些细节之处没有讲到，并且因为水平有限，难免有很多错误和不足之处，希望大家多加指正。在以后的文章中，我也许会将用补码实现的高精度的代码奉上。