数字电路是怎么实现除法的？
数字电路是怎么实现除法的？
如8/5=1
有没有个算法的描述？
问题点数：50、回复次数：8Top
1 楼steedhorse（晨星）回复于 2005-04-03 18:26:13 得分 0
好像有一种实现是通过移位依次求出5 * (2 ^ n)的所有小于8的值，然后依次尝试从8中减去这些值。Top
2 楼steedhorse（晨星）回复于 2005-04-03 18:42:04 得分 10
比如说，这样就可以通过减法和移位实现整除：
int devide(int m, int n)
{
assert(m >= 0 && n > 0);
int i = n;
while(i <= m)
i <<= 1;
int j = m;
while(j > n) {
i >>= 1;
if(j > i)
j -= i;
}
return j;
}
当然，这顶多也就算个“可行性”验证。真正CPU里头的整除部件所用的逻辑肯定比这高效得多，不过具体是什么算法，偶也不知道。：PTop
3 楼97ce_twinkle（毛毛虫）回复于 2005-04-04 09:59:43 得分 0
找本《计算机组成原理》——白中英，
第二还是第三章看一看
Top
4 楼dengsf（drklnk@Radical_Dreamer）回复于 2005-04-04 11:57:03 得分 20
steedhorse(晨星) 说的其实就是类似于我们实际里所用的 试除法，
缺点是如果估计的商大时这步就白做了。
实际里对整数的除法好像有一种叫 加减交替法，不必回退的。我 *想* CPU里对整数除法可能就用这个了。
而对浮点的除法，我见过介绍好像有一种是用 牛顿迭代法 的,用加法和乘法部件实现除法的。
比如求 a/x，先用迭代法求出 y=1/x 的倒数，然后再做一次 a*y 的乘法就行了。具体如下：
它限制 1/2 <= x <= 1（实际CPU里有格式化的东西要求最高位为1，所以这个前提是有意义的），并置初值 y0约＝1.5 （根据限制条件，初值跟实际值的误差 <= 1/2）；
迭代时，置 y(i+1) = 2*yi - x*yi*yi。
结合x的范围可以得出，如果 |yi - 1/x| <= e, 则 |y(i+1) - 1/x| <= e^2。这样对于 n 位精度的数，只需要 log2(n) 次迭代就得出符合精度要求的结果了。
intel的CPU浮点加、乘好像只要几个时钟周期，而除法需要几十个周期，所以很可能它就是用了这种方法的～～Top
5 楼zzwu（未名）回复于 2005-04-04 15:23:10 得分 0
除法通常化为减法来做的。Top
6 楼rickone（RickOne）回复于 2005-04-05 12:14:56 得分 0
我的一个师兄说是用逻辑电路方法实现的,就是列真值表,然后列出逻辑表达式,然后化简,然后设计电路,用什么与门,或门连起来....
加法的实现我知道,一个全加器,输入Xi,Yi:两个加数,输入低位进位Ci-1,输出结果Si和高位进位Ci,然后列真值表,最后做成电路,然后用8个全加器串接就构成一个8位的加法器,,,
除法可不可以这么类似的做?那真值表怎么列?应该也有与'进位'类似的数值吧???Top
7 楼steedhorse（晨星）回复于 2005-04-05 12:42:01 得分 0
除法用真值表的话，即使8bit的寄存器，真值表也要256 × 256那么大啊。
不懂，关注。Top
8 楼zzwu（未名）回复于 2005-04-05 17:38:19 得分 20
除法在计算机中肯定用减法来实现的，但通常要结合“移位”操作。
不用移位、只用减法，也可以实现的，但速度较慢。
减法则用补码的加法来实现。
加法（2进制）则非常方便：a,b相加，则结果的本位值是“a异或b”，而进位值是“ a与b”。
移位的实现则非常非常方便。
Top
