Logarithmic time integer division using bit shift addition and subtraction only

Question

I was asked to implement integer division with logarithmic time complexity using only bit shifts, additions and subtractions.

I can see how I can deal with a divisor which is a power of 2, but how can I deal with an odd divisor, such that the time remains logarithmic?

Is it even possible?

EDIT: a way to do it in a time complexity that isn't logarithmic but still better than linear will also be welcomed.

Thanks

Answer 1

It's just like doing long division on paper but in binary. You shift bits from the divided into an accumulator until it's at least as large as the divisor, then subtract the divisor from the accumulator and continue until you've processed all the bits all the while recording a 0 for every shift w/o a subtract and a 1 for every time you do subtract.

15/5 (1111/101)
dividend accumulator result
1111      0000       0  - can't subtract, shift
1110      0001       0  - can't subtract, shift
1100      0011       0  - can't subtract, shift
1000      0111       0  - can subtract, set 1
1000      0010       1  - can't subtract, shift
0000      0101       10 - can subtract, set 1
0000      0000       11 - we're done since we shifted 4 times

The answer is 3 (11).

The top bit of the dividend shifts into the bottom of the accumulator. The result is shifted every time the dividend/accumulator are shifted.

It's logarithmic in time for the value of the dividend, not the number of bits in the dividend.