欢迎光临散文网会员登陆 & 注册

计算机组成-四则运算

2023-07-19 21:48 作者:~Sakuno酱 0人读过 | 我要投稿

无符号减法运算

计算机的加减法是以 $2%5En$ 为模的加法

也就是说 $x%3D2%5En-1$ 那么计算机对 $x$ 加一后会得到 $0$

$2%5En%20%5Cequiv%200%20%20%5Cmod%202%5En$

利用这个特性可以设计出减法

例如

$x%2B%20%5Clnot%7Bx%7D%20%5Cequiv%202%5En-1$

$x%2B%5Clnot%20x%2B1%5Cequiv%200$

如果 $y%3Ex$

就有

$y%2Bx%2B%5Clnot%20x%2B1%5Cequiv%20y$

$y%2B%5Clnot%20x%2B1%5Cequiv%20y-x$

所以减法可以转换成加法来算补码就是这样来的

无符号乘法计算

这个也很简单就是移位

$r$ 表示算数移位

$xy%3Dx(y_0%2B2y_1%2B..2%5E%7Bn-1%7Dy_%7Bn-1%7D)$

记 $a_i%3D2%5E%7Bi%7Dx$

$xy%3D%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7Dy_ia_i%3D%5Csum_%7Bi%3D0%7D%5E%7Bn-1%7Dy_i(a_%7Bi-1%7D%20%5Clll%201)$

无符号除法计算

这个理解有点复杂

记 $y$ 是除数 $x$ 是被除数

$x%3DQy%2Br%20%20$ $0%20%5Cle%20r%20%3C%20y$

如果 $Q%3Dq_0%20%2B2q_1%20%2B..%202%5E%7Bn-1%7Dq_%7Bn-1%7D$

那么就有

$x%3Dq_0y%20%2B2q_1y%20%2B..%202%5E%7Bn-1%7Dq_%7Bn-1%7Dy%20%2Br$

所以

$r%3Dx-q_0y-q_1(2y)%20-%20%20...-q_%7Bn-1%7D(2%5E%7Bn-1%7Dy)%20%3C%20y$

于是我们可以通过以下算法计算 $r$

$a_0%3Dx$

$a_%7Bi%2B1%7D%3D%20%5Cbegin%7Bcases%7D%0Aa_i%20%20%26%20a_i%3C2%5E%7Bn-(i%2B1)%7Dy%20%20%5C%5C%0Aa_i%20-2%5E%7Bn-(i%2B1)%7Dy%20%26%20a_i%20%5Cge%202%5E%7Bn-(i%2B1)%7Dy%20%5C%5C%0A%5Cend%7Bcases%7D$

这样计算下去就有了 $r%3Da_n$

下面是证明过程

首先可以用数学归纳法证明 $a_i%20%5Clt%202%5E%7Bn-i%7Dy$

因为除数不能为 $0$ 所以必然有 $a_0%20%3D%20x%5Clt%202%5En%20%5Cle%202%5Eny$

假设有 $a_k%20%5Clt%202%5E%7Bn-k%7Dy$

对于 $a_%7Bk%2B1%7D$ 来说如果 $a_k%20%5Clt%202%5E%7Bn-(k%2B1)%7Dy$ 那么 $a_%7Bk%2B1%7D%3Da_k%20%5Clt%202%5E%7Bn-(k%2B1)%7Dy$

如果 $%202%5E%7Bn-(k%2B1)%7Dy%20%5Cle%20a_k%20%5Clt%202%5E%7Bn-k%7Dy$

那么 $a_%7Bk%2B1%7D%3Da_k-2%5E%7Bn-1-k%7Dy%20%20%5Clt%202%5E%7Bn-k%7Dy-2%5E%7Bn-(k%2B1)%7Dy%20$

$%202%5Ccdot2%5E%7Bn-(k%2B1)%7Dy-2%5E%7Bn-(k%2B1)%7Dy%20%20%3D%202%5E%7Bn-(k%2B1)%7D$

所以有 $a_k%20%5Clt%20a%5E%7Bn-k%7Dy$

那么必然有 $0%20%5Cle%20a_n%20%5Clt%20y$

此外有 $x%20%5Cequiv%20a_0%20%5Cequiv%20a_1...%5Cequiv%20a_n$

标签：

计算机组成-四则运算的评论 (共条)