Question ：
Divide two integers without using multiplication, division and mod operator.
Anwser 1 ：
[cpp]
class Solution {
public:
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ret = 0;
if(dividend == 0 || divisor == 0) return 0;
int sign = 1; // 1 : positive; -1 : negative
if(dividend < 0) sign *= -1;
if(divisor < 0) sign *= -1;
long long tmpDiv = dividend;
long long divL = abs(tmpDiv);
long long tmpDivisor = divisor;
long long divisorL = abs(tmpDivisor);
while(divL >= divisorL){
int count = 1; // first: divL > divisorL
long long sum = divisorL; // long long, cal divisorL
while(sum + sum <= divL){
count += count;
sum += sum;
}
divL -= sum;
ret += count;
}
return sign * ret;
}
};
注意点：
1） 原理：累加除数，判断是否大于被除数
2） 设置符号位sign，判断符号
3） 对dividend和divisor都先转化成long long类型，防止负数转化成正整数时溢出
4） 除数之和sum，必须设置成long long，防止溢出（同2）
Anwser 2 ：
[cpp]
class Solution {
public:
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
long long a = dividend;
long long b = divisor;
int sign = 1;
if(a < 0){
a = -a;
sign *= -1;
}
if(b < 0){
b = -b;
sign *= -1;
}
int d = 0;
while ( (b << d) <= a )
{
++d;
}
--d;
int res = 0;
for (int i = d; i >= 0; --i) {
if ( (b << i) <= a ) {
res += (1 << i); // high to low
a -= (b << i); // remaider
}
}
return sign * res;
}
};
Anwser 3：
[cpp]
class Solution {
private:
long long f[100];
public:
int bsearch(long long a[], int left, int right, long long key)
{
if (left > right)
return -1;
int mid = left + (right - left) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] < key)
{
int pos = bsearch(a, mid + 1, right, key);
return pos == -1 ? mid : pos;
}
else
{
return bsearch(a, left, mid - 1, key);
}
}
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int sign = dividend < 0 ? -1 : 1;
if (divisor < 0)
sign *= -1;
long long div = dividend;
div = abs(div);
long long divisorL = divisor;
divisorL = abs(divisorL);
f[0] = divisorL;
int size = 1;
while(true)
{
if (f[size-1] >= div)
