Divide 2 integers@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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

» Solve this problem

In the first beginning, I use minus operator to minus the divisor each time, until the dividend is smaller than the divisor. Though this method can work out, yet it is toooo slow. Especially in the case that the dividend is too large while the divisor is too small.

So we can use the bit operation here.

See the algorithm below. It move the divisor one step left each time, so the divisor*2 each time. Then dividend-divisor, and count+=1<<i. When dividend minus i times of divisor, then, count will add i correspondingly.

In the mean time, we need to pay attention to the positive/negative sign of dividend and divisor.
We use(dividend^divisor)>>31. Why move 31 steps right? Because the highest bit represent the sign of an integer.

There are two solutions given below. The second one can pass the tests. Because we can see that it let's the divisor grows in exponential order.

There are some places we need to pay attention is,
1. Use long long instead of int. Because INT_MIN = -INT_MAX-1, thus when we transfer the dividend or divisor to abs value, if one of them is INT_MIN, after transferring, it will overflow.

2. We need to define as long long a = dividend, then a = abs(a). We can't do long long a = abs(dividend). Otherwise the type won't be changed.

3. XOR bit manipulation. The rule is F^F = F, T^T = F, T^F = T. Means when two things are the same, it will be F, otherwise it will be T.