计算a+b我们可以先计算a^b==c、a&b==d;c是a与b不进位相加的结果,d看作是a+b的进位,进位是向高位进位的所以需要通过移位来将c和d进行对齐后再相加,c和d如何相加呢?与a+b一样。当进位为0即没有进位时相加就可以结束了,最后一次异或的结果即是a+b的结果。
a-b可以看做是a+(-b),如何得到-b呢?(~b)+1即是-b。
代码模拟如下步骤:
以180/7举例:
180/7=25=
二进制中的每一个bit可以看做是:
那么我们可以借助乘法,将 [7∗,7∗] 中的所有数依次比较,如果其中某个数x小于等于180 我们则将结果ans的对应bit置1并将180减去x。
除此之外我们还要考虑溢出的问题,因为一个数乘以 是极易造成溢出的, 溢出后的结果x(通常是负数)往往总是小于等于180的所以我们可稍微改进一下:(180>>>i)>=7,这与原来地判断是等价的,因为一个数乘以就是将它左移i位,相反一个数除以就是将它右移i位。
但这只是较为理想的情况,因为我们还没有考虑负数。
如果a、b都为负数,那么a/b==(-a)/(-b)。
如果a、b中某一个为负数,那么a/b==-|a|/|b|
这个在上述代码实现的基础上还需要给除法加上一些特判, 主要是处理除数或被除数为整数最小值的情况,因为Java中整数最小值的绝对值不等于整数最大值。
特判如下:
都是最小值返回1
被除数是最小,除数为1返回最小
被除数是最小,除数为-1返回最大
被除数是最小,除数不为负数返回(被除数+除数)/除数-1
被除数是最小,除数为负数返回(被除数-除数)/除数+1
除数是最小,返回0
评论