Thursday, December 20, 2012

[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:  }  

No comments: