Detailed Explained 8ms C++ solution


  • 285

    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; 
        }
    };

  • -1
    L

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


  • 0

    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 :-)


  • 0
    L

    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.


  • 0

    Hi, lalatiantian. You are always welcome :-)


  • 0
    H

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


  • -4
    H

    I google the labs,it is return the long int 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 !divisor to divisor==0


  • 0

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


  • 0
    H

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


  • 0

    Hi, you are welcome :-)


  • 30
    L

    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 :)


  • 0
    L

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


  • 0

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


  • 0

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


  • 0
    R

    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!


  • 0

    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.


  • 0
    R

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


  • 0
    K

    labs = long abs


  • 0

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


  • 0

    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?


Log in to reply
 

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