Divide Two Integers
解题思路
一开始想的比较简单，直接减法做，毫无意外的超时了。
发现大学比较熟悉的二进制除法竟然一点点也想不起来的，并且，直接不会算了，真是越来越回去了。
先看一个二进制除法的例子：
// 十进制 10/3 -> 1010 / 11
二进制除法
从上图可以看出此二进制除法的过程（其实与十进制除法类似），通过不断地除数左移和减法实现了此除法过程，因此，类似的，本题中的除法算法可以描述如下：
- 约定：被除数~ a,除数~ b,商~ result
- 为方便计算，a,b取正
- 枚举除数左移位数，从31到0，循环
- b左移i位得t，判断a是否大于t，如果是，则result+=1，a-=t
- 每次循环，result左移一位
- 判断result符号，同号正，异号负
- 注意：此题中还有一个坑是数据的范围。Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.
即input范围[−2^31, 2^31 − 1]，但是结果可能会溢出，溢出时返回 2^31 − 1。
因此，开始对数据进行了特殊处理，并且计算过程统一使用了long long int。
代码如下（C++）：
class Solution {
public:
int divide(int dividend, int divisor) {
if(dividend == INT_MIN && divisor == -1)
return INT_MAX;
if(divisor == 0) return 0;
long long int a = abs((long long int)dividend), b = abs((long long int)divisor);
long long int result = 0;
int c = 32;
while(c) {
c--;
long long int t = b << c;
result <<= 1;
if(a >= t) {
a -= t;
result += 1;
}
}
if((dividend >= 0) ^ (divisor >= 0)) result = -result;
return result;
}
};
