[LeetCode] Divide Two Integers

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

解题思路：

考虑到可能会溢出，因此可用long long类型强制转化int类型。另外，这种类型题目一般都是先确定符号位，将所有的值转化成正数，然后再进行相关操作。（与之前的分数转循环小数类似）

另外，注意32位的int类型的最大值和最小值形式。我的算法有点不美，就是可能在位数不同的机器上结果不对。若有更好办法，，欢迎留言。

class Solution {public:int divide(int dividend, int divisor) {int MIN_INT = 1 << 31;int MAX_INT = 0x7fffffff;if (divisor == 0){return MAX_INT;}long long result = 0;//先确定符号bool positive = (dividend ^ divisor) >= 0 ? true : false;long long dividendL = (long long)dividend;long long divisorL = (long long)divisor;//取绝对值if (dividendL < 0){dividendL = -dividendL;}if (divisorL < 0){divisorL = -divisorL;}//为0的情况，不做判断也可以workif (dividendL < divisorL){return 0;}while (dividendL >= divisorL){long long base = 1;long long tempDivisorL = divisorL;while (dividendL >= (tempDivisorL << 1)){ //考虑到右移运算会让被除数失真，因此用除数左移tempDivisorL <<= 1;base <<= 1;}result += base;dividendL -= tempDivisorL;}if (!positive){result = -result;}//判断是否溢出if (result>MAX_INT || result<MIN_INT){return MAX_INT;}return (int)result;}};

如果困难是地上的荆棘，我们脱掉鞋子，光着脚笑笑，