反转 64 位算术中的乘法

Question

我正在尝试用 64 位整数进行一些乘法和除法运算。我希望我的结果有 64 位，任何溢出都应该被截断。我已经设法让它与乘法一起工作：

z = 0xed5c6911
y = 0xFFFFFFFF & (z * 33)

print hex(z)
print hex(y)

这输出：

0xed5c6911
0x98e98b31

符合预期。

我现在要撤销这个：

z = 0xFFFFFFFF & (y / 33)
print hex(z)

我期望 0xed5c6911，z 的原始值，但我得到 0x4a23a85。

如何反转第一个片段中的操作并从 y 中检索 z 的原始值？

Answer 1

此操作不可逆。当您将 z 乘以 33 时，您会将最上面的第 64 位推到超过 64 位限制并通过溢出破坏信息。

可以看到0xed5c6911的二进制值using google.

换句话说，您需要使用比 64 位更宽的数据类型来执行此操作。例如，您可以使用 long:

z = long(0xed5c6911)
y = long(0xFFFFFFFFFFFF) & (z * 33) # Note the added F's
print hex(z)  # 0xed5c6911L
print hex(y)  # 0x1e98e98b31L

使用long你可以反转这个操作：

z = 0xFFFFFFFFFFFF & (y / 33) # Again, note the added F's
print hex(z) # 0xed5c6911L

Answer 2

您将无法从 y 中检索 z 的原始值。

当您在第一个示例中截断 (z * 33) 的乘法时，您将丢失信息 - 在本例中为高位。然后，当您进行除法时，您将除以一个不同的值 (z * 33)，因此将无法恢复 z。

为了实际取回 z，您需要存储一些额外的信息 - 最简单的方法是使用具有更多位的数据类型。

Answer 3

更新： harold 发表评论后：您的掩码只有 32 位 - 为了掩码 64 位，您需要用 & 0xFFFFFFFFFFFFFFFF.

以下是32位:

可以反转操作：通过截断为 32 位，您可以有效地在整数环 Z/2^32 Z 中进行计算。 33 确实有一个 modular multiplicative inverse 在那里：

1/33 = 0x3e0f83e1  mod  2^32

所以对于任何 32 位数字，您可以通过与上面的数字相乘（并截断为 32 位）来反转乘以 33。

您可以使用 extended euclidean algorithm. mathematically this in the domain of number theory.

求逆

请注意，这个环中只有奇数有倒数（2 是 2^32 的唯一质因数）。

对于 64 位 33 的倒数是：

1/33 = 0x0f83e0f83e0f83e1  mod  2^64

Reversing a multiplication in 64 bit arithmetic