不使用算术运算符计算 x/y

Question

我目前正在 python 中完成 "Elements of Programming Interview"，但卡在了这一部分。下面的代码只是简单地将两个数字相乘，而不使用任何运算符；作者给出的解释如下：

We can compute the largest k such that (2^k)y <= x, subtract (2^k)y from x, and add 2^k to the quotient. For example is x = (1011) and y =(10), then k = 2, since 2 x 2^2 <= 11 and 2 x 2^3 > 11. We subtract (1000) form (1011) to get (11), add 2^k = 2^2 = (100) to the quotient, and continue by updating x to (11).

A better way to find the largest k in each iteration is to recognize that it keeps decreasing. Therefore, instead of testing in each iteration whether (2^0)y, (2^1)y, (2^2)y, ... is less than or equal to x, after we initially find the largest k such that (2^k)y <= x, in subsequent iteration we test (2^k-1)y, (2^k-2)y, (2^k-3)y, ... with x. For the example given earlier, after setting the quoient to (100) we continue with (11). Now the laegest k such that (2^k)y <= (11) is 0, so we add 2^0 = (1) to the quotient, which is now (101). We continue with (11) - (10) = (1), Since (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

我的问题是：

算法是如何工作的（概述）
乳清功效 = 32
为什么我们要按幂 (32) 移动 y
y_power代表什么
为什么我们要给结果加 1 << 幂

Answer 1

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

如果我们想用 x 除以 y，我们问自己 "how many times does y fit into x if we add as many zeros to it as possible?"。 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，如果不适合，将 "move it one digit to the right"。

result += 1 << power

完成后，它只会将 "number of how many times y shifted left fits into 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 添加到结果中。然后我们从 x = 1111 中减去 y_power = 1010 得到 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.

不使用算术运算符计算 x/y

Compute x/y without Arithmetical Operators

python

algorithm

binary

bit-manipulation

bitwise-operators