My clear cpp code


  • 0
    C
    class Solution {
    public:
        int divide(long dividend, long divisor) 
        {
            if(divisor == 0) return ~(1<<31);
            
            long long res = 0;
            
            long long divend = dividend;
            long long divsor = divisor;
            
            int sign = (dividend^divisor)>>31 != 0 ? -1 : 1;
            
            divend = abs(divend);
            divsor = abs(divsor);
            
            // divend = 2^k * divsor + m;
            // then m = 2^m * divsor  + r , 
            // r = ....., repeat the process
            while(divend >= divsor)
            {
                long long shiftCnt = 0;
                long long tmp = divsor;
                while((tmp << 1) <= divend)
                {
                    tmp <<= 1;
                    shiftCnt++;
                }
                
                divend -= tmp;
                // !!!!!!!!!!!! use long long to avoid overflow !!!!!!!!!!!
                res += ((long long)1<<shiftCnt);
            }
            
            // !!!!!!!!!!!! use long long to avoid overflow !!!!!!!!!!!
            if (res >= ((long long)1)<<31 && sign == 1)
                return ~(1 << 31);
            
            return res*sign;
        }
    };

  • 0
    A

    While this works, doesn't the problem say not to use the multiplication operator, which you used when determining the sign?

    Or perhaps the problem hinted at not used the multiplication operator for the purpose of getting the quotient, but I'm not sure.


Log in to reply
 

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