c - 按位乘法得到结果

Question

是否有一套通用的规则来通过将已知数和未知数相乘来达到某个数。例如假设 x = 13 且 z = 9

有没有办法找到 y 使得

    x * y = z     
=> 13 * y = 9

我不想将它们用作数学整数，而是用位表示。所以，我想将 z 保留为一个整数。显然，位表示中存在溢出，但我不确定如何在不强制 32 位机器中的所有值的情况下找到 z。我认为 y 是一个非常小的负数。

注意:这不是硬件分配，因此您可以将 x 和 y 更改为任何值，这些只是示例。

Answer 1

首先，找到 modular multiplicative inverse x (13) mod 2³²。有几种方法可以做到这一点，很多人会推荐扩展欧几里德算法，但对于这种情况来说它并不是最简单的。有关更简单的算法，请参阅 Hacker's Delight 第 10 章(整数除以常数)。

无论如何，一旦您知道 13 mod 2³² 的模乘逆是 0xc4ec4ec5，将该数字乘以 z 得到 y。

0xc4ec4ec5 * 9 = 0xec4ec4ed

所以y = 0xec4ec4ed，0xec4ec4ed * 13确实是9。

请注意，如果 x 是偶数，则它没有倒数。如果它“至多与 z 一样”(即它的尾随零的数量与 z 一样多或更少)，则可以在除掉它们的最高值后以这种方式解决2 的常用幂。