[LeetCode] Divide Two Integers 解题报告

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

两个数的除法，但是不允许用乘、除、取余符号。

[解题思路]
如果可以用乘的话，二分搜索倒是不错的解法。
否则，只能寄希望于位符操作了。

 基本思想就是把除数向左移位(×2)然后与被除数比较，直到发现仅次于被除数的那个值，减去该值后继续。也可以用递归做，这里图省事，就是一个循环了事。

[Code]

1:  int divide(int dividend, int divisor) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int sign = 1;  
5:      if(dividend ==0) return 0;  
6:      if(dividend <0) sign*=-1;  
7:      if(divisor <0) sign *=-1;  
8:      unsigned int dvd = dividend >0? dividend: -dividend;  
9:      unsigned int dvs = divisor >0? divisor: -divisor;//abs(divisor);  
10:      unsigned int inc[32];  
11:      unsigned int migValue = dvs;  
12:      int i =0;  
13:      while(migValue > 0 && migValue <= dvd)  
14:      {  
15:        inc[i] = migValue;  
16:        migValue = migValue <<1;  
17:        i++;  
18:      }  
19:      i--;  
20:      unsigned int res = 0;  
21:      while(i>=0 && dvd!=0)  
22:      {  
23:        if(dvd >= inc[i])  
24:        {  
25:          dvd = dvd - inc[i];  
26:          res += 1<<i;  
27:        }  
28:        i--;  
29:      }  
30:      res*= sign;  
31:      return res;  
32:    }  

[做题中的几个错误]
1. Line 8，Line 9， Line10, Line 11
    一开始用的是Int，而不是Unsigned Int。带来的一个最直接的问题就是，如何处理INT_MIN(-2147483648)，比如 abs(-2147483648) = -2147483648。而进位的时候也麻烦，比如1073741824<<1， 结果不是2147483648， 而是-2147483648。所以把他们全部换成unsigned Int， 以避开这种麻烦。
2. Line 11 and Line 12
   刚开始的时候，两行并成一行：
unsigned int migValue = dvs，i =0;
在替换完所有的int为unsigned int以后，立即犯了一个疏忽。
在处理比如（1,2）时，返回值是16777248， 而不是0。
原因就在于，当i被改为unsigned int后，如果i==0， i--会导致i变为2147483647， 而不是-1。
所以，拆分成两行，i的定义不变，仍然为int。
3. Line 21
   一开始只有 while（i>=0）， 没有剪枝，当dvd ==0的时候，没必要继续循环。加一个剪枝条件。

这个题目是蛮有意思的。这种数据溢出细节的处理倒是以前没有注意过。也是第一次发现原来abs(INT_MIN)的值居然还是INT_MIN。直觉上，INT_MIN的这种特性，应该跟补码有关，但是懒得深究了。


Update 08/21/2014 重新看了一下，简单的事情搞复杂了。关于溢出的问题，直接用unsigned long就解决了，省了很多不必要的比较和判断。

1:  int divide(int dividend, int divisor) {       
2:       unsigned long dvd = dividend < 0 ? -dividend : dividend;  
3:       unsigned long dvs = divisor < 0 ? -divisor : divisor;  
4:       if (dvd < dvs) return 0;  
5:       int sign = 1;  
6:       if (dividend < 0) sign *= -1;  
7:       if (divisor <0) sign *= -1;  
8:       unsigned long absDivisor = dvs;  
9:       int step = 0;  
10:       while (dvs < dvd)  
11:       {  
12:            dvs = dvs << 1;  
13:            step++;  
14:       }  
15:       unsigned long result = 0;  
16:       while (dvd >= absDivisor)  
17:       {  
18:            if (dvd >= dvs)  
19:            {  
20:                 dvd -= dvs;  
21:                 result += (unsigned long) 1 << step;  
22:            }  
23:            dvs = dvs >> 1;  
24:            step--;  
25:       }  
26:       return result * sign;  
27:  }