仅使用移位加法和减法的对数时间整数除法 [英] Logarithmic time integer division using bit shift addition and subtraction only

问题描述

我被要求仅使用移位，加法和减法来实现具有对数时间复杂度的整数除法.

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

我可以看到如何处理2的幂的除数，但是如何处理奇数的除数，以使时间保持对数?

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?

有可能吗?

在时间复杂度上不是对数但仍比线性更好的一种方法也将受到欢迎.

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

谢谢

推荐答案

就像在纸上做长除法一样，但是用二进制进行.您可以将位从除法器移位到累加器中，直到其大小至少等于除数，然后从累加器中减去除数，然后继续操作，直到对所有位都进行了处理，同时每次移位都记录为0，且减去和每次减去都会为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

答案是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.

这篇关于仅使用移位加法和减法的对数时间整数除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！