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:

Handle special cases first (overflow, zero, division by 1)
Determine sign using XOR of sign bits
Convert both numbers to negative (this handles the INT_MIN case better)
Use doubling technique: keep doubling the divisor until adding another copy would exceed the dividend
Subtract that doubled amount and add the corresponding count
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 Conversion Find Common Characters