前言:

本来是在看汇编里面的数据条件传送指令,做习题的时候看着这么一道有关于2的幂次方除法的题目。结果傻眼了,又尼玛不会了。。。。。。。。。第二章看的时候就稀里糊涂的,看了几遍也没看太懂,这回又涉及到了 ,发现再回来看还是容易一点。所以写此博文,方便日后复习。

我今天遇到的问题如下:

计算机中如何实现除数是2的幂次的除法【转载自CSDN】-LMLPHP

计算机中如何实现除数是2的幂次的除法【转载自CSDN】-LMLPHP

计算机中如何实现除数是2的幂次的除法【转载自CSDN】-LMLPHP

问题:

除法,在我们平时的算数运算中,结果总是向0的方向舍入的,但是在计算机中,舍入的方式有所不同。在大多数的机器中,除法要比乘法还有加法这些运算都要慢很多倍,计算机中对于2的幂次这种数很是敏感,因为计算机当中用到的指令和进制本来就是二进制的形式,计算机用这种方式运算是最快的。所以,在做除法时如果除数是2的幂次,那么我们就可以进行一些优化,让运算做到更加快速。

解决办法:

因为左移运算相当于是乘以2,右移运算相当于除以2.所以说当我们的除法的除数是2的幂次方的时候,利用单纯的移位运算要比利用普通方法快的多。

对于无符号数来说, 如果除数是2的k次幂,那么我们就会把被除数啊相应的做算数右移操作,右移k位。这样的结果和平时我们做除法的结果是一样的。

对于无符号数来说,假设x是一个有w位的二进制数,x'是从第w位到k位的序列,x''是0-k位的序列。那么x' =floor(x/2^k),这个表达式是可以证明的,过程还是很easy的我就不多说了。

对于一个无符号数还有一个有符号数的非负数来说的话,除以2的k次幂和把被除数右移k位的结果是一样的

计算机中如何实现除数是2的幂次的除法【转载自CSDN】-LMLPHP

计算机中如何实现除数是2的幂次的除法【转载自CSDN】-LMLPHP

但是对于有符号数的负数来说,就会有一些差错。

计算机中如何实现除数是2的幂次的除法【转载自CSDN】-LMLPHP

计算机中如何实现除数是2的幂次的除法【转载自CSDN】-LMLPHP

在 十进制那一栏里面是计算机的计算结果舍入之后的结果,最右边一栏是计算机算的结果,我们可以看出来,在整除也就是不需要舍入的时候,结果和右移k位的操作是一样的,但是如果一旦没有整除需要进行舍入的时候,我们就会发现出了问题了,移位导致它不是向0舍入而是向下舍入,-771.25按理说应该舍入为-771,但是他却舍入到了-772.

在平时进行手算除法的时候,我们的结果统一都是向0舍入的,但是在计算机中确实向下舍入,因为非负数向下舍入就是向0舍入所以不会有影响,但是负数的话就不会了。因为移位之后,负数在左边补充的是最高的符号位,而不是0.负数在做除法的 时候应该是向上舍入才符合手算中向0舍入的规则。

对于负数除法向0舍入的解决办法:

为了保证正确的舍入方式,我们决定利用一个偏置值来解决这个问题。

对于任何整数x和y>0,有ceil(x/y) = floor((x+y-1)/y)

假设x=ky + r (r>=0 && r < y span>

我们就可以清楚(x+y-1)/y = (ky+ r - 1)/y = k + (r + y - 1)/y

如果此时x能整除y,即r = 0,那么ceil(x/y) = floor((x+y-1)/y) = k

否则的话等于k + 1那么也就是说,在计算被除数是负数,除数是2的幂次的除法的时候,可以给x加上除数-1(y-1)这个偏移量,即可保证除法的结果是正确的,因为在除数是2的幂次的时候,才能够用右移操作来进行替代,则当被除数是负数的时候,要给他加上2^k - 1这个偏移量,才能够得到正确的结果。

所以在计算机内如果除数是2的幂次的时候,是会用向下面的这个表达式的形式去计算除法的的

(x < 0 x k -x >> k

05-16 21:53