如何使用二元运算将整数除以 3

Question

类似问题：如何知道一个二进制数是否能被3整除？

但是如何仅使用二元运算来有效地将数字除以 3？

Answer 1

主要思想是以下观察：

1/3 = 1/4 + 1/16 + 1/64 + ... 

并记住除以 4 是一个简单的二进制运算（两位移位）。 现在，由于我们处理的是整数，它可能无法被 4 的幂整除，因此我们必须进行适当的修改。令

x_0

为可被 3 整除的整数。我们有：

x_0 = 4*q_0 + r_0

其中

q_0 = x_0 // 4

和

r_0 = x_0 % 4

，或者换句话说，

q_0 = x_0 >> 2

，

r_0 = x_0 & 0b11

。

为此

q_0

，我们有

x_0 - 3*q_0 = q_0 + r_0 

我们将

q_0

添加到累加和中，现在我们需要除

x_1 := q_0 + r_0

，我们知道它可以被 3 整除，并且比

x_0

小（大约两位）。迭代这个想法，同时

x_k > 3

，诱导序列

q_0 + q_1 + ... + q_k

加起来就达到了想要的结果，

x_0 / 3

。

至于运算，我们有：位移位、AND 和加法。加法只需使用 AND 和 XOR 的二元运算即可实现。这是一些代码：

def binary_sum(a, b):
    while True:
        add = a ^ b  # '^' is XOR
        carry = a & b

        if carry == 0:
            break
        else:
            a = add
            b = carry << 1

        return add

def bin_division_by_3(x):
    sum = 1

    while x > 3:
        q, r = x >> 2, x & 0b11
        sum = binary_sum(sum, q)
        x = binary_sum(q, r)

    return sum