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

• 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;
}
};``````

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

• You are right. Fixed.

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