Divide two integers without using multiplication, division and mod operator.
class Solution {
public:
int divide(int dividend, int divisor) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int y = dividend;
int x = divisor;
bool signFlag = 0;
if (y > 0){
y = -y;//defualt for
dividend = y;
signFlag = 1;
}
if (x > 0){
x = -x;//both negatives
divisor = x;
signFlag = !signFlag;
}
// 10|11
// 00|01
int totalShift = 0;
while(y < x){
++totalShift;
y >>= 1;
}
if (y == x) ++totalShift;
--totalShift;
// |divisor<<totalShift| <= |dividend|
int result = 0;
for(y = dividend, x = divisor<<totalShift;//y <= x
totalShift >= 0;
--totalShift){
result <<= 1;
if (y <= x){
++result;
y -= x;
}
x >>= 1;
}
if (signFlag){
result = - result;
}
return result;
}
};
No comments:
Post a Comment