[LeetCode] 028: Divide Two Integers

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

[Analysis]
注意：while(a > (b << cnt) && cnt <= 100)cnt++;
这个很重要，使用a > (b << cnt)而不使用a >= (b << cnt)，是因为a和b可能相等，且为很大的数，b移位后溢出，将进入死循环。
使用cnt <= 100卡一下，是因为b可能是1，而a是非常大的数。

[Solution]

class Solution{
   
public:
	int divide(int dividend, int divisor){
   
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		// zero
		if(dividend == 0 && divisor == 0)return 1;
		if(dividend == 0)return 0;

		// set flag
		int flag = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
		unsigned int a = abs(dividend);
		unsigned int b = abs(divisor);

		// divide
		int res = 0;
		while(a >= b){
   
			int cnt = 0;
			while(a > (b << cnt) && cnt <= 100)cnt++;
			if(cnt > 0)cnt--;
			res += (1 << cnt);
			a -= (b << cnt);
		}
		return res * flag;
	}
};

说明：版权所有，转载请注明出处。 Coder007的博客