Divide Two Integers
题目描述
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
整除两个整数，不能使用乘除，取模。
思路：
题目考的是位运算，求出除数的最大位移数max，使用被除数-1<<max，使用剩余的数继续计算。
注意特殊值的情况。
public class Solution {
public int Divide(int dividend, int divisor) {
if(dividend == 0){
return 0;
}
if(divisor == 0){
return dividend > 0 ? int.MaxValue : int.MinValue;
}
long x1 = dividend;
long x2 = divisor;
var negtive = false;
if(x1 < 0){
x1 = -x1;
negtive = !negtive;
}
if(x2 < 0){
x2 = -x2;
negtive = !negtive;
}
long result = 0;
long remain = x1;
while(remain >= x2)
{
var shifts = S(remain, x2);
remain -= x2 << shifts;
var v = 1<< shifts;
result += v;
//Console.WriteLine(remain + ","+ v);
}
if(negtive){
result = -result;
}
if(result < 0 && (result + int.MaxValue < 0)) //// less than int.MinValue
{
return int.MaxValue;
}
return (int)result;
}
private int S(long x, long y){
int count = -1;
while(x >= y){
x>>=1;
count ++;
}
return count;
}
}