leetcode 29 整数相除 c语言

int divide(int dividend, int divisor) {
   //唯一可能的越界情况
   if(dividend == INT_MIN && divisor == -1)
       return INT_MAX;
   //单独对divisor == INT_MIN 进行的处理
   if(divisor == INT_MIN)
       return dividend==INT_MIN?1:0;

int flag = 0;
int ans = 0;

   //判断两个int是否同符号
   if((dividend^divisor)&0x80000000)
       flag = 1;

   int plus = 0;

   //负转正可能越界
   if(dividend<0)
   {
       if(dividend==INT_MIN)
       {
           //单独处理越界情况
           plus = 1;
           dividend = INT_MAX;
       }
       else
       {
           dividend = -dividend;
       }
   }

   if(divisor<0) divisor = -divisor;

   for(int i=31;i>=0;--i)
   {
       if(divisor<=(INT_MAX>>i))
       {
           if(dividend >= (divisor<<i))
           {
               dividend = dividend - (divisor<<i);
               if(plus)
               {
                   dividend +=plus;
                   plus = 0;

               }
               ans += (1<<i);
           }
       }
   }

//下面注释错误
   //由于plus存在导致原本可以整除，但是实际上缺失plus导致的不能整除轮后裔
   //例如：8/2
   //8/8 ans =8

   //7/4 ans = 4
   //(3+1)/2 ans = 4+2
    //2/1   ans = 4+2+1
   //最后仍剩余1
   //只有在dividend = INT_MIN时候出现
   while(dividend >= divisor)
   {
       ans ++;
       dividend -=divisor;
   }

   return flag?-ans:ans;

}

评论实际上没有考虑INT_MIN/1的情况导致ans越界

恰巧答案一致，所以通过。

最后的while(dividend >= divisor)也不是因为plus导致的

因为程序是以 a=b*2^n+b*2^(n-1)+...+b

防止b溢出，所以判断了 b<=INT_MAX/2^n

实际上b*2^n==INT_MAX+1的时候没有溢出

导致判断溢出错误。

可以改为下面的判断方法

leetcode 29 整数相除 c语言

-------------------------------------------------------------------------------

网上改进：

可以通过long long divid = dividend;

从而省掉plus

但是注意 divid = (long long )INT_MAX +1 ;//必须这么写不然编译器认为右面是int会越界，给divid就成了INT_MIN的值

-------------------------------------------------------------------------------

网上改进2：

leetcode 29 整数相除 c语言

相关推荐