前言:
本来是在看汇编里面的数据条件传送指令,做习题的时候看着这么一道有关于2的幂次方除法的题目。结果傻眼了,又尼玛不会了。。。。。。。。。第二章看的时候就稀里糊涂的,看了几遍也没看太懂,这回又涉及到了 ,发现再回来看还是容易一点。所以写此博文,方便日后复习。
我今天遇到的问题如下:
问题:
除法,在我们平时的算数运算中,结果总是向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位的结果是一样的
但是对于有符号数的负数来说,就会有一些差错。
在 十进制那一栏里面是计算机的计算结果舍入之后的结果,最右边一栏是计算机算的结果,我们可以看出来,在整除也就是不需要舍入的时候,结果和右移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