问题：
给定 被除数 和 除数，不借助 乘法、除法、模运算，实现除法运算。
Example 1: Input: dividend = 10, divisor = 3 Output: 3 Explanation: 10/3 = truncate(3.33333..) = 3. Example 2: Input: dividend = 7, divisor = -3 Output: -2 Explanation: 7/-3 = truncate(-2.33333..) = -2. Note: Both dividend and divisor will be 32-bit signed integers. The divisor will never be 0. 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 231 − 1 when the division result overflows.
解法：bit位方法
运用bit位移动法：
对被除数，每次减去，除数*2^n（商=2^n），进行尝试。
例如：
- 尝试，商为2：除数（bit位）<<1 等价于：除数*2
- 尝试，商为4：除数（bit位）<<2 等价于：除数*4
- 尝试，商为8：除数（bit位）<<3 等价于：除数*8
直到尝试到，被除数-除数*2^(n+1)<0
那么，被除数>除数*2^n
商一定首先包含2^n。
然后用剩下的 被除数-除数*2^n 作为新的被除数尝试对象，继续进行上面的尝试。
loop依此类推，
可得：
被除数=除数*2^n+除数*2^m+除数*2^l+...+除数*2^0+余数(不够<除数)
=除数*(2^n+2^m+2^l+...+2^0)+余数
由于题意，余数被省略掉。
所求res则为：2^n+2^m+2^l+...+2^0
⚠️ 注意：边界问题：INT_MAX和INT_MIN的bit运算，则尽量使用更大的空间，保证不会overflow，因此使用long long类型对题意的int进行操作。
代码参考：
1 class Solution { 2 public: 3 int divide(int dividend, int divisor) { 4 unsigned int res=0; 5 unsigned int did = abs(dividend), dvs = abs(divisor); 6 if(dividend == INT_MIN && divisor == -1) return INT_MAX; 7 while(did >= dvs) { 8 long long tmp = dvs; 9 int i = 0; 10 for(i=0; (tmp<<1) <= did; i++) { 11 tmp = tmp << 1; 12 } 13 res += (1<<i); 14 did -= tmp; 15 } 16 return (dividend>0^divisor>0)?-res:res; 17 } 18 };
根据bit特点，最多移动31位，for从大到小进行一次尝试即可。
1 class Solution { 2 public: 3 int divide(int dividend, int divisor) { 4 unsigned int res=0; 5 long long did = abs(dividend), dvs = abs(divisor); 6 if(dividend == INT_MIN && divisor == -1) return INT_MAX; 7 for(int i=31; did >= dvs; i--) { 8 if(did >= (dvs<<i)) { 9 res += (1<<i); 10 did -= dvs<<i; 11 } 12 } 13 return (dividend>0^divisor>0)?-res:res; 14 } 15 };