Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
class Solution {
public:
int divide(int dividend, int divisor) {
//First check whether the final result will encounter overflow
if(!divisor || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
//We use long to store the final reslut,
//because we convert the negative number to positive
//If dividend is -2^31, we need to make sure that we will not have overflow
long divd = labs(dividend);
long divs = labs(divisor);
//Save the sign, if both of them or neither of them are negative,
//bit xor operation will return flase, sign will be 1.
int sign = ((dividend<0)^(divisor<0))?-1:1;
int finalRes = 0;
while(divd>=divs){
long temp = divs;
int multiple = 1;
//We update temp to 2* temp every time, in oder to save time
//We use the myltiple to keep track of how many times we have shifted our temp,
//We use bit left shift to synchrosize the operation, for each for loop,
//we can say that 2 * previous multiple divisor can be subtracted from the dividend.
//multiple will add to final result
while(divd>=(temp<<1)){
temp = temp<<1;
multiple = multiple<<1;
}
//If dividend - temp is still greater than divisor, we need to calculate from multiple = 1 again.
divd -= temp;
finalRes += multiple;
}
return sign>0? finalRes:-finalRes;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment