Simple old-school O(logn) manual division using pen and paper in C++


  • 0
    X

    The following computes the quotient the same way we did in primary school w/ a pen and a piece of paper. The core algorithm listed under "manual division" is very simple. Much of the rest is to handle overflow.

    class Solution {
    public:
        int divide(int dividend, int divisor) {
            if (0 == divisor)       return INT_MAX;
    
            bool is_neg = dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0;
            // use unsigned int to accommodate abs(INT_MIN)
            int n = sizeof(int) << 3;
            unsigned nominator = dividend != INT_MIN ? abs(dividend) : (1U << n - 1);
            unsigned denominator = divisor != INT_MIN ? abs(divisor) : (1U << n - 1);
    
            // manual division
            unsigned result = 0;
            for (int i = n - 1; i >= 0; i--) {
                if ((nominator >> i) >= denominator) {
                    nominator -= (denominator << i);
                    result |= (1 << i);
                }
            }
    
            // potential overflow
            if ((1U << n - 1) == result)
                return is_neg ? INT_MIN : INT_MAX;
            return is_neg ? -((int)result) : result;
        }
    };

  • 0
    P

    I dont think , your code handles {-2147483648, -1}


  • 0
    X

    You are right. Fixed.


Log in to reply
 

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