Bit manipulation as the best submission, still along with two tricks


  • 3

    bit manipulation

    class Solution {
    public:
        //AC - 4ms - reusing the previous temporary value to reduce redundant calculation;
        int divide(int dividend, int divisor) 
        {
            if((dividend==INT_MIN && divisor==-1) || divisor==0) return INT_MAX;
            int sign = (dividend<0 ^ divisor<0)? -1 : 1;
            long dd = abs((long)dividend), dv = abs((long)divisor);
            if(dd < dv) return 0;
            int h = 0;
            long t = dv;
            while(t <= dd) t <<= 1, h++;
            long ret = 1 << --h;
            dd -= (t>>=1);
            while(dd >= dv)
            {
                while(t > dd)
                    t >>= 1, h--;
                ret |= 1<<h;
                dd -= t;
            }
            return ret*sign;
        }
    };
    

    using div

    class Solution {
    public:
        int divide(int dividend, int divisor)
        {
            if(dividend==INT_MIN && divisor==-1) return INT_MAX;
            div_t divresult = div(dividend, divisor);
            return divresult.quot;
        }
    };
    

    using log

    class Solution {
    public:
        int divide(int dd, int dv) 
        {
            int sign = (dd<0 ^ dv<0)? -1 : 1;
            if(dd==INT_MIN && dv==-1) return INT_MAX;
            long dd1 = abs((long)dd), dv1 = abs((long)dv);
            if(dd1 < dv1) return 0;
            if(dv1 == 1) return sign*dd1;
            return sign*exp(log(dd1)-log(dv1));    
        }
    };
    

Log in to reply
 

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