Leetcodes Solution 29 Divide Two Integers

zhuanlan.zhihu.com

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

If it is overflow, return MAX_INT.

思路1

使用位運算

比如dividend = 15， divisor = 3

3 右位移4次等於12，5次等於24，15 = 3 * 4 + 3

然後剩下的餘數在用上面的操作，再右位移一次，最後得到的答案是5次

class Solution{public: int divide(int dividend, int divisor){ if(!divisor || dividend == INT_MIN && divisor == -1) return INT_MAX; int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1; long long dvd = labs(dividend); long long dvs = labs(divisor); int res = 0; while(dvd >= dvs){ long long temp = dvs, multiple = 1; while(dvd >= (temp << 1)){ temp <<= 1; multiple <<= 1; } dvd -= temp; res += multiple; } return sign == 1 ? res : -res; }};

推薦閱讀：