[Leetcode] divide two integers 两数相除

Divide two integers without using multiplication, division and mod operator.

题意：两数相除不能用乘法、除、取余运算。

思路：直观的想法是相减，使用计算器p记下相减的次数n，这样时间复杂度为O(n)（n代表相减次数）。这是如两数相差较大，则n很大时，容易超时。所以我们应该想一个办法加速相减的过程，那如何了？在被除数大于等于除数的情况下（若小于，则相除为0，直接返回即可），我们可以将除数乘以2（即除数扩大一倍）和被除数比较，如还是小于，则继续乘以2，直到若当前值乘以2以后大于被除数，即能通过乘2得到的小于被除数的最大值temp。记下乘以2的次数，用被除数减去这个temp，用剩下的值重复上述过程。这样的做的原因是因为一个整数可以用二进制的形式表示，比如：99表示为1100011，这种做法相当于先去掉最高位的1，然后一次去掉后面的1.

那又有一个问题：如何在不能运用乘法的基础上乘以2，这是我们可以运用位操作 ，向左移动一位相当于乘以2。

像sqrt、pow数字处理的题目都要注意边界的问题。

 1 class Solution {
 2 public:
 3     int divide(int dividend, int divisor) 
 4     {
 5         if(divisor==0||dividend==INT_MIN&&divisor==-1)
 6             return INT_MAX;
 7 
 8         bool sign=((dividend<0)^(divisor<0))?true:false;
 9         long long divid=labs(dividend),div=labs(divisor); //labs()函数是对长整型数求绝对值。
10         int res=0;
11         if(divid<div)   return 0;
12         while(divid>=div)
13         {
14             long long temp=div,p=1;
15             while(divid>=(temp<<1))
16             {
17                 temp<<=1;
18                 p<<=1;
19             }
20             divid-=temp;
21             res+=p;
22         }
23         return sign?-res:res;    
24     }
25 };

注：fabs()函数是对浮点数求绝对值；labs()函数是对长整型数求绝对值。参考了LeetCode OJ