|||
限位数——你想到会有什么用吗?
姜咏江
计算机能够准确地进行算术运算,归功于有了限位数运算的理论。我在研究SAT问题快速计算的过程中,又总结出了一些限位数非常有用的性质。这些性质使纯离散因素计算成为了可能。
1. 限位数定义
什么是限位数?数码位数确定的数就是限位数。
限位数组成的是无符号整数。限位数的无效0不能省略。计算机中的算术运算,就是通过固定位数的无符号整数加法,通过特别的判定方法,实现了实数的算术运算。有关这方面的问题,可参考《自己设计制作CPU与单片机》一书的第10章。
2. 限位数性质
本文主要介绍限位数非数值计算的一些性质。为了简单,可就3位二进制数加以测试。
定义1 两个数码之和为最大数码,一个为另一个的反码。
定义2 将一个数的数码用对应的反码替换,得到的数是原数的反码数。
性质1 k位N进制数最多有Nk个。
定义3 Nk个k位N进制不重复数称为全块。
性质2 全块各位置每个数码都有Nk-1个。
性质3 互为反码数之和为最大数。
性质4 二进制非反码数至少有一位数码相同。
性质5 k位N进制不重复数一位有相同数码Nk-1个,这些数其余位组成的是k-1位全块。
以上限位数的各性质读者都可以自己证明。这些性质十分简单,但在用子句消去法快速求逻辑电路满足解的问题中,起到了根本性的作用。
2016-12-6
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-11 02:13
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社