强基初中数学&学Python——外加课 负整数向右位移的系统错误与纠正方法


  先看下面相反数向右位移的情况。

>>>53>>1, -53>>1

(26, -27)

>>>54>>1, -54>>1

(27, -27)

>>>54>>2, -54>>2

(13, -14)

  绝对值相同的两个数,位移后有的绝对值相等,有的不等,显然这里有算法上的错误。由位移的方法规范可知正整数向右位移一定不会出问题,那么问题一定出在负整数向右位移。

  为此,用八位整数图解上面负整数的向右位移过程。

 

 

 

  出现错误因为移除的位不全0造成。为何不全0会造成计算错误呢?由图可以看到,如果不全0,那么原来由原码转为储存码过程中的加1操作就被恢复了,意思就是从来就没有加1;但移位后转回原码,减1操作继续进行,也就是说因为右移,该数平白无故地减1,造成结果比正常结果小1。

  我们无法改变这种移位操作,但可以纠正它的错误。在移位前检查被移除的位置有无1,如果有那么结果加1,否则不加。

>>>53>>1, (-53>>1)+1 if -53 & 0b1 >0 else -53>>1

(26, -26)

>>>54>>1, (-54>>1)+1 if -54 & 0b1 >0 else -54>>1

(27, -27)

>>>54>>2, (-54>>2)+1 if -54 & 0b11 >0 else -54>>2

(13, -13)

 

  用Java语言测试出现同样的错误,应该是硬件算法问题。

  练习题:设计一个位移函数,使这个函数具有纠正负整数右移系统错误的功能。