想问下leetcode 29一个神奇的地方

class Solution {
    public int divide(int dividend, int divisor) {
        if(divisor == 1) return dividend;
     if(dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE; //overflow

     boolean isNeg = (dividend > 0) ^ (divisor > 0);
     int res = 0;

     dividend = Math.abs(dividend);
     divisor = Math.abs(divisor);

     while(dividend - divisor >= 0) {
      int temp = divisor;
      int mul = 1;
      while(dividend - (temp << 1) >= 0) {
       temp <<= 1;
       mul <<= 1;
      }
      dividend -= temp;
      res += mul;
     }
     return isNeg ? -res : res;      
    }
}


在跑testcase : dividend = 2147483647  , divisor = 2， 第二个while循环换成while(dividend >= (temp << 1))会超时，理论上不是一样的吗，一直没想通，是overflow的问题吗，求指教

2^31=147483648刚好比那个数大1，那这肯定溢出了啊，第一种写法可以是因为除了*2溢出，-法也溢出了，-负数就是加，，，后面不行是因为大于等于右边是个负数啊

jyyzzj 发表于 2020-6-14 08:19
2^31=147483648刚好比那个数大1，那这肯定溢出了啊，第一种写法可以是因为除了*2溢出，-法也溢出了，-负数 ...

明白了，2 << 31得到的是-2147483648，所以死循环了，非常感谢🙏

跟overflow有关系。因为dividend是0111,1111,...,1111。首位是符号位。2的二进制表示是10，不停左移，会得到1000,0000,...,0000也就是-2147483648，这个值你和第一个数比较的话，第一个数更大，通过了while的判断。而且之后temp左移会不停得到0，所以就死循环了。但是你用第一个数减第二个数，此时溢出，二进制表示会得到1111,1111,...,1111也就是-1.这时候是小于0的，第二个while就终止了

不知道小帅 发表于 2020-6-14 08:29
跟overflow有关系。因为dividend是0111,1111,...,1111。首位是符号位。2的二进制表示是10，不停左移，会得 ...

👍