# Detailed Explained 8ms C++ solution

• In this problem, we are asked to divide two integers. However, we are not allowed to use division, multiplication and mod operations. So, what else can we use? Yeah, bit manipulations.

Let's do an example and see how bit manipulations work.

Suppose we want to divide `15` by `3`, so `15` is `dividend` and `3` is `divisor`. Well, division simply requires us to find how many times we can subtract the `divisor` from the the `dividend` without making the `dividend` negative.

Let's get started. We subtract `3` from `15` and we get `12`, which is positive. Let's try to subtract more. Well, we shift `3` to the left by `1` bit and we get `6`. Subtracting `6` from `15` still gives a positive result. Well, we shift again and get `12`. We subtract `12` from `15` and it is still positive. We shift again, obtaining `24` and we know we can at most subtract `12`. Well, since `12` is obtained by shifting `3` to left twice, we know it is `4` times of `3`. How do we obtain this `4`? Well, we start from `1` and shift it to left twice at the same time. We add `4` to an answer (initialized to be `0`). In fact, the above process is like `15 = 3 * 4 + 3`. We now get part of the quotient (`4`), with a remainder `3`.

Then we repeat the above process again. We subtract `divisor = 3` from the remaining `dividend = 3` and obtain `0`. We know we are done. No shift happens, so we simply add `1 << 0` to the answer.

Now we have the full algorithm to perform division.

According to the problem statement, we need to handle some exceptions, such as overflow.

Well, two cases may cause overflow:

1. `divisor = 0`;
2. `dividend = INT_MIN` and `divisor = -1` (because `abs(INT_MIN) = INT_MAX + 1`).

Of course, we also need to take the sign into considerations, which is relatively easy.

Putting all these together, we have the following code.

``````class Solution {
public:
int divide(int dividend, int divisor) {
if (!divisor || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
long long dvd = labs(dividend);
long long dvs = labs(divisor);
int res = 0;
while (dvd >= dvs) {
long long temp = dvs, multiple = 1;
while (dvd >= (temp << 1)) {
temp <<= 1;
multiple <<= 1;
}
dvd -= temp;
res += multiple;
}
return sign == 1 ? res : -res;
}
};``````

• I think only the type of temp should be set as long. There is no need to do so to dvd, dvs and multiple.

• Hi, lalatiantian. I modify the code is modified in this way and it fails. If you have an accepted solution of this modification, could you share it with me? Thanks :-)

• Sorry, I didn't fully understand at the first time. You are right. The variable dividend and divisor might be the minimum value of integer, so they should be transformed to long if we want to get their absolute value, which I have ignored.

• Hi, lalatiantian. You are always welcome :-)

• what means "labs"? i changed abs to labs. it was sloved my problem, thank you!

• I google the labs,it is return the `long in`t type it's range is also the same to the `int` type of (`-2147483648,2147483647`).I am confused about why when changed to labs ,the answer is right.
by the way , i think you should change the code `!diviso`r to `divisor==0`

• Hi, huzhp. What is the difference between `!divisor` and `divisor == 0`?

• sorry. I made a wrong reminder.
I used to think that add "！"before a negative number will become positive.

• Hi, you are welcome :-)

• great idea! but I think we should not use long (what if they give you two long input?) since it's a int problem. Here is how I handle the dividend == Integer.MIN_VALUE case:

public class Solution {

``````public int divide(int dividend, int divisor) {
//other code...
if(dividend==Integer.MIN_VALUE){
if(divisor==-1) return Integer.MAX_VALUE;
else if(divisor==1)  return dividend;
else return ((divisor&1)==1)?divide(dividend+1,divisor):divide(dividend>>1,divisor>>1);
}
if(divisor==Integer.MIN_VALUE) return 0;
//other code continue...
}
``````

}

Hope will make sense :)

• another tiny problem: it doesn't allow to use * operator. (the last line) :)

• Hi, liji94188. Thank you for your nice remind. I have updated the last line to be `return sign == 1 ? res : -res;`.

• Hi, liji94188. I guess I have got your idea and it would be good to avoid using `long long` as you did.

• HI, I just don't understand why when divisor&1 == 1, dividend(dividend+1, divisor) == dividend(dividend, divisor) works? Can you explain it to me? Thanks!

• Hi, rlaoyao. You may just try some examples since this case only appears when `dividend == Integer.MIN_VALUE`. BTW, `divisor & 1 == 1` simply means `divisor` is an odd number.

• Thanks! I have understood it. Actually, I wonder how can he come up with such a solution.

• labs = long abs

• Hello, I find you are really good at mathematics. Any way, thank your very much for your detail explanation.

• First, are you avoiding the use of long long, or avoiding the use of long?

I assume you are avoiding the use of long.
I think this code still cannot walk around integer overflow.
since temp = dvs is an integer. temp << 1 can still have overflow,
Thus the original code: while (dvd >= (temp << 1))
may have weird result.
Is it correct?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.