[LeetCode] 29. Divide Two Integers

轉自LeetCode

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

If it is overflow, return MAX_INT.

<Solution>

這題要來算除法，但是不能用乘除以及餘數的運算子

用加減來算，速度會太慢

還有一個方法，就是用 bit operation

• 每次把除數乘2 (左移一位)，看是不是還小於被除數。如果小於，就重覆此步驟；如果大於，被除數減掉最後的數字

• 同時間也要記錄，到底乘二了多少次

• 重複上述步驟，直到被除數小於除數

用個例子說明 : 102 / 5

round 1: 102 / 5，quotient = 0

被除數    除數    記數
 102      5      1
 102      10     2
 102      20     4
 102      40     8
 102      80     16

round 2 : (102 - 80) / 5，quotient = 16

被除數    除數    記數
 22       5      1
 22       10     2
 22       20     4

22 - 20  = 2 < 5，結束

quotient = 16 + 4 = 20 = 102 / 5

code 如下

	class Solution {
	public:
	int divide(int dividend, int divisor) {
	if(divisor == 0 || (dividend == INT_MIN && divisor == -1)) {
	return INT_MAX;
	}
	else if((divisor == 1 && dividend > 0) || (divisor == -1 && dividend < 0)) {
	return abs(dividend);
	}
	long m = abs((long) dividend), n = abs((long) divisor);
	if(m < n) {
	return 0;
	}
	long quotient = 0;
	//> use bit operation to find quotient
	while(m >= n) {
	long cnt = 1;
	long tmp = n;
	while(m >= (tmp << 1)) {
	tmp <<= 1;
	cnt <<= 1;
	}
	quotient += cnt;
	m -= tmp;
	}
	if((dividend < 0) ^ (divisor < 0)) {
	//> is negative
	quotient = -quotient;
	}
	return (quotient > INT_MAX) ? INT_MAX : quotient;
	}
	};

view raw divideTwoInt.cpp hosted with ❤ by GitHub