My C++ code, 8ms


  • -2
    D

    Use long long to avoid overflow in the calculation. First, detect two corner cases : divide-0 and INT_MIN/-1 and return INT_MAX directly. Then do the division via bit shift and minus operations. Say z = x/y and z in binary bit format is z_31, z_30, z_29, ... z_0, the while loop is to detect those non-zero bits of z and combine them to get z. (for example, x=11, y =2, z =5 = (0x101)) , Through while loop, we will get shift =2 (bit 2 of z is nonzero) first, then get shift = 0 (bit 0 of z is nonzero). so res = 1<<2 + 1<<0 = 5;

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            if(!divisor) return INT_MAX;
            if(dividend== INT_MIN && divisor==-1) return INT_MAX;
            long long x = dividend>0 ? dividend: -(long long)(dividend), y = divisor>0 ? divisor:-(long long)(divisor);
            int shift=32, res =0;
            bool neg = (dividend>0) ^ (divisor>0);
            while(x>=y)
            {
                while( x < (y<<shift)) --shift;
                res |= 1<< shift;    
                x -= (y<<shift);
            }
            return neg?-res:res;
        }
    };

Log in to reply
 

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