By yusijia

Updated:

Contents

/*

  • Divide two integers without using multiplication, division and mod operator.
  • If it is overflow, return MAX_INT.
    */
  • 题意：
    模拟除法, 不允许使用除法, 乘法, 取模操作
1
2
3
4
5
6
7
8
9
10
11
使用加法, 减法, 位运算操作模拟
例如: 
a    c   b左移的位数
420  20  1
400  40  2
360  80  4
280  160 8
120  20  1
100  40  2
60   20  1
40   40  2

class Solution {
public:
int divide(int dividend, int divisor) {
bool sign = true;
if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)){
sign = false;
}

    long long a = dividend >= 0 ? dividend : -(long long)dividend;
    long long b = divisor  >= 0 ? divisor  : -(long long)divisor;

    long long result = 0, c = 0;

    while (a >= b) {
        c = b;      //b一直没变, 用c去代替他
        for (int i = 0; a >= c; i++) {
            a -= c;
            result += (1<<i);
            c <<= 1;
        }
    }

    return sign ? min((long long)INT_MAX, result) :
                  max((long long)INT_MIN, -result);
}

};

Contents