The idea is to get back to the original purpose of the operation of division: n/d
is to count how many d
's we could find from the total n
.
Without losing generality, assuming both n > 0, d > 0
.

 For first round, build up and check the last number in geometric sequence
d, 2*d, 4*d, ...
which is not exceedingn
.
 For first round, build up and check the last number in geometric sequence

 Record the coefficient
k
found in Step 1 and reducen
byk*d
.
 Record the coefficient

 Repeat Steps 1 and 2 and keep building up sum of found coefficients.
Finally, the total sum of found coefficients will be the answer. Overflow handling need to take care of when coefficient sum is reaching INT_MAX
, where we need to immediately return.
int divide(int n, int d) {
bool negative = (n < 0)^(d < 0);
int res = 0; long nn = abs((long)n), dd = abs((long)d);
while (nn >= dd) {
long x = dd, count = 1;
while (x < nn>>1) { x<<=1; count<<=1; }
res += count; nn = x;
if (res == INT_MIN) return negative? INT_MIN : INT_MAX; // overflow handling
}
return negative? res : res;
}