姜咏江

什么是限位数？就是数码位数一定的数。以往人们并没有注意对限位数的研究，是因为人们极少用到它。现在人们用电脑了，用电脑要解决问题，在设计上就不得不考虑位数一定的数，而且要考虑怎样用位数一定的数来表达实数。当然这个问题首先是计算机设计专家碰到的问题。在计算机中只有不带符号的二进制整数，而且是限定了位数的32位、64位或128位等。人们不可能造出位数无限长的计算机，因而用限位数来表示和运算来解决实数的运算问题，是首先要解决的问题。实际上这个问题已经基本上解决了。解决最彻底是我在十多年前完成的限位数理论和方法，在计算机算术运算器的设计中有着根本性的作用。不管人们是否认可，它就放在那里。

这两年多，我研究SAT问题多项式时间复杂度算法，对限位数的使用又有了新的发现。如果把过去研究限位数看作只是一维的研究方法，那么针对SAT问题，已经进入了二维空间的研究。毫无疑问，这种研究为破解难题SAT问题，找到了坚实的理论基础，为那些需要整体结构分析才能够解决的难题，打开了一扇大门。

关于限位数在数值计算当中的基本原理，我在《自己设计制作CPU与单片机》一书中已经介绍。对于限位数二维空间的特点，本文就做一点简单的介绍，目的是让人们能够理解SAT问题如何利用子句消去法完成计算求解。

为了简单，仅就二进制限位数的一些基本性质述说。

1. k位二进制数最多有2^k个，叫全块。

2. k位二进制数全体，每位0和1都有2^k-1个。

3. 将数码0和1互换得到的数叫反码数。每一个限位数都有唯一反码数。

4. 反码数之间每位数码都不同，非反码数之间至少有一位数码相同。

   
   

   限位数在子句消去法中的应用：

   SAT问题可以用0和1表示成一张表。表中的每一行就是一个限位数，叫子句。

如果我们将变量的值设定为0，那么这一列每个为0的子句的值就是1。按照逻辑运算的法则，就不影响对其余子句是否值为1的判断，因而可以消去。上表是全块，不论如何设定变量的值，都不可能让全部子句值为1，一定会有子句剩下。显然，不是全块，就可能设定变量值将全部子句消去。只要非全块中有一个变量有2^k-1个0或1，那么这个变量就有唯一解。用这种全局结构的判断就可以逐步地求出SAT的解，而无需考虑多次猜测性的重来。

当变量同时在不同的子句块中出现时，要比单一子句块复杂，但用上面限位数的性质，就可以找到那些只有唯一值的变量，通过这些变量的值确定，最终可达到求出SAT的解。当然，如果SAT本身就无解，子句消去法在求解的过程中，可发现无解的全块和有唯一解的矛盾的情况。

二维的限位数值得我们深入地进行研究。目前在解决SAT问题满足解中只是露出了头角而已。

2016-12-19