Skip to content

    Fast Division Without Multiplication

    We need to watch out for overflow. But we also need to make our algorithm fast by reducing the number of operations.

    The key insight: instead of subtracting the divisor one at a time, we double it each step until we can’t anymore. This cuts down computation dramatically.

    int divide(int a, int b) {
    if (a == INT_MIN && b == -1) {
        return INT_MAX;
    } else if (a == 0) {
        return 0;
    } else if (b == 1) {
        return a;
    }

    int neg=(a>>31)^(b>>31);
    // Range is -2^31 to 2^31-1  
    // Negative range is larger. Convert everything to negative.
    if (a>0) a=-a;
    if (b>0) b=-b;
    if (b<a) return 0;
    int sub=b;
    int step=1;
    int res=0;

    while(true) {
        // Double the step size to reduce calculations when possible
        while(sub >= (INT_MIN/2) && a - (sub+sub) < 0) {
            sub+=sub;
            step<<=1;
        }
        a-=sub;
        res+=step;
        // Reset to original step size
        step=1;
        sub=b;
        if (a > b) {
            break;
        }
    }

    return neg ? -res : res;
}

    The algorithm works by:

    1. Handle special cases first (overflow, zero, division by 1)
    2. Determine sign using XOR of sign bits
    3. Convert both numbers to negative (this handles the INT_MIN case better)
    4. Use doubling technique: keep doubling the divisor until adding another copy would exceed the dividend
    5. Subtract that doubled amount and add the corresponding count
    6. Reset and repeat with remaining value

    This beats simple repeated subtraction by cutting the number of iterations from O(n) to O(log n).

    #overflow

    Excel Sheet Column Title ConversionFind Common Characters