今天在刷到这道题,《剑指offer》上实现了两数相加,想了一下两数相减的思路
设被减数x=10,减数y=7,那么一次异或后:
1010
^ 0111
1101
两数相减,0^0=0,0^1=1,1^0=1,1^1=0,可以发现只有0-1的时候,我们需要向高位借位,但是当前为答案也是0^1的结果。
那么我们下步目标,应该求出那些位置是需要向高位借位的。其实一次异或后的结果&减数,位置为1的都是需要借位的。因为相应的位置可以反推出被减数是0,减数是1。
所以就有类似于两数相加的思路:
然后,我就在思考,那么8-10会得出正确的答案么,事实上也是正确的。
因为a<b,所以b会不断得向高位借位,导致b溢出,变成了-2147483648(2^-31),负数和正数异或时,也是需要变成补码后,再操作,最后再变回源码。
ps:b变成-2147483648过程:b会不断左移,知道变成int能表示的最大值,2^31-1(最高位为0 ,表正数),左移1位,最高位是1,变成了int能表示的最小数了。而且-2147483648的补码就是本身,因为按照正常去推补码,答案应该是0,但是0的源码,反码,补码都是0,这样会形成冲突,所以,我们规定了-2147483648补码是本身。