Divide Two Integers - c++编程基础

1.Problem

Divide two integers without using multiplication, division and mod operator.If it is overflow, return MAX_INT.

2.Pre-Thought

题目要求不能使用乘法、除法和求余运算符，只能使用+、-运算符。

除法可理解为被除数是由几个除数相加得到的，比如8 / 2 = 4,可写成8 = 2 + 2 + 2 + 2; 7 / 2 = 2 + 2 + 2 + 1,商为3.

那么可以用减法不断地用除数去减被除数，一直到被除数小于除数为止。

3.Example

3.1普通模式: dividend = 70, divisor = 2

1) 70 - 2 = 68 -----> factor = 1,

minus = 2,

res = 0 + factor = 1

2) 68 - (2 + 2) = 66 ----->factor = factor + factor= 2,

minus = minus + minus = 4,

res = res + factor = 3

3) 66 - (4 + 4) = 54 -----> factor = factor + factor = 4,

minus = minus + minus = 8,

res = res + factor =7

... ...

3.2特殊情形1: divisor = 0

溢出，输出整数最大值INT_MAX（头文件是limits.h）

3.3特殊情形2: divisor = 1

直接输出dividend

3.3特殊情形3: divisor = -1

1）如果dividend == INT_MIN，则溢出，因为最大整数的绝对值总比最小整数绝对值小1. 此时，直接输出INT_MAX，表示结果溢出。

（普及知识： "INT_MIN"和"INT_MAX"是在头文件中定义的，在32位操作系统中，INT_MAX为2^32-1=2147483647.INT_MIN为-2^32=-2147483648.）按照数学知识，（-2^32）/（-1）应该为2^32，但是2^32这个数超出了正数的表示范围.）

2）否则，输出dividend的相反数，也即0 - dividend

3.4特殊情形4: dividend < 0, divisor < 0

1）如果divisor == INT_MIN，则结果必须为0. 2）否则， 如果dividend == INT_MIN, abs(dividend) == dividend.也即最小整数的abs绝对值仍然为它本身，这时，只能对 divident先赋值为INT_MAX，并进行第一步减法后，加上1.（比如abs(-8) = -8,如果只有4位）。

4.Algorithm

1）对dividend和divisor均取绝对值，一方便进行正整数相减的工作;

2）首先对第3步考虑到的特殊情形，进行特殊处理;

3）对普通模式进行处理时需要注意的两点是:

a)minus + minus有可能溢出，需要进行判定。如果minus + minus < 0,则溢出。需要进行第二次外层while循环，对factor和minus重新初始化; b)当dividend - minus < 0时，需要进行第二次外层while循环，对factor和minus重新初始化;

5.Coding

#include
  
   
#include
   
     // import abs #include
    
      using namespace std; class Solution { public: int divide(int dividend, int divisor) { int MAX_INT = INT_MAX; // 如果除数为0,那么就输出MAX_INT if(divisor == 0) return MAX_INT; // 如果除数为1,那么就输出dividend if(divisor == 1) return dividend; // 如果除数为-1,那么就输出-dividend if(divisor == -1) { if(dividend == INT_MIN) return MAX_INT; return 0 - dividend; } // 求取除数和被除数中负数的个数 int minus = 0; if(dividend < 0) minus += 1; if(divisor < 0) minus += 1; dividend = abs(dividend); divisor = abs(divisor); int res = 0; // 处理INT_MIN的除法(divisor=INT_MIN)，因为abs(INT_MIN)=INT_MIN if(divisor == INT_MIN) { if(dividend == INT_MIN) return 1; else return 0; } bool flag_min = false; if(dividend == INT_MIN) { flag_min = true; dividend = INT_MAX; } // 如果被除数小于除数，则输出0 if(dividend < divisor) return 0; // 如果被除数不小于除数，则做减法操作 while(dividend >= divisor) { int factor = 1; res += factor; int minus_current = divisor; dividend -= minus_current; if(flag_min) { flag_min = false; dividend += 1; } while(true) { int minus_temp = minus_current; minus_current += minus_current; if(minus_temp >= 0 && minus_current < 0) break; int temp = dividend - minus_current; if(temp < 0) break; else { dividend = dividend - minus_current; if(flag_min) { flag_min = false; dividend += 1; } res = res + factor + factor; factor = factor + factor; } }; } // 如果商应该是负数,那么就对结果取相反数 bool flag = minus & 1; if(flag) res = 0 - res; return res; } }; int main() { int a = INT_MIN; int b = a + 1; int res = 0; Solution sol; res = sol.divide(a, b); cout<