在没有算术运算符的情况下计算x / y Download

  

我们可以计算出最大的k，使得（2 ^ k）y <= x，减去（2 ^ k）y   从x开始，将2 ^ k加到商中。例如x =（1011）和y   =（10），则k = 2，因为2 x 2 ^ 2 11。我们减去（1000）形式（1011）得到（11），再加上2 ^ k = 2 ^ 2 =（100）的商，   并继续将x更新为（11）。

     

在每次迭代中找到最大k的更好方法是识别   它一直在减少。因此，而不是在每个测试中   迭代（2 ^ 0）y，（2 ^ 1）y，（2 ^ 2）y，...是否小于或等于   在我们最初找到最大的k使得（2 ^ k）y <= x之后   随后的迭代我们测试（2 ^ k-1）y，（2 ^ k-2）y，（2 ^ k-3）y，...   X。对于前面给出的示例，将商数设置为   （100）我们继续（11）。现在最大的k使得（2 ^ k）y <=   （11）是0，所以我们将2 ^ 0 =（1）添加到商（101）。   我们继续（11）-（10）=（1），因为（1）

def divide(x, y):

    result, power = 0, 32
    y_power = y << power

    while x >= y:

        while y_power > x:

            y_power >>= 1
            power -= 1

        result += 1 << power
        x -= y_power

    return result

我的问题是：

1. 算法如何工作（概述）
2. 为什么功率= 32
3. 我们为什么要按幂移动y（32）
4. y_power代表什么
5. 我们为什么要加1 <<幂到结果

1 个答案:

答案 0 :(得分：2)

这是二进制数的长除法。您可能是在学校学习十进制数字的。

如果我们想将x除以y，我们就会问自己：“ y是否适合x多少次？ ？”。向y添加n个零等同于乘以2 ^ n或向左移n。

power = 32
y_power = y << power

该算法的第一个猜测是向y添加32个零，这将其向左移动power。因此，如果您知道结果可能> = 2 ^ 33，则必须为power使用较大的初始值。

while y_power > x:
   y_power >>= 1
   power -= 1

在内部循环中，它将测试y_power是否已经适合x，如果不是，则将“向右移动一位”。

result += 1 << power

完成此操作后，它将只在结果中写入“ y左移适合x的次数”。就像二进制数一样，它可以是零或一，并且内部循环跳过了所有零，所以它必须是一。

x -= y_power

从长除法中可以知道，我们现在需要从被除数中减去除数y的倍数，然后继续计算结果。

while x >= y:

如果该差异y小于x，我们将停止，因此2 ^ power * y不可能适合x。

示例 让我们计算15/5：

 1111 / 101 = 11
-1010
------
  101
 -101
------
    0

为简便起见，我们有x = 1111和y = 101，并从power=1开始。首先，我们计算y_power = y<<power = 101<<1 = 1010。由于1010 > 1111为假，因此我们跳过内部循环，并将1<<power = 1<<1 = 10添加到结果中。然后我们从y_power = 1010中减去x = 1111，得到101。现在y_power = 1010 > 101 = x是真实的，我们递减power，所以我们得到power = 0和y_power = y<<power = 101。现在y_power>x再次为假，我们将1<<power = 1添加到结果中并得到x - y_power = 0。现在x >= y为假，我们以result = 11结尾。