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