c++ - 如果你有另一个因素和溢出的产品，你如何计算一个因素？

Question

a * x = b

我有一个看似相当复杂的乘法/imul 问题:如果我有 a 和 b，如果它们都是 32 位双字(例如 0-1 = FFFFFFFF、FFFFFFFF+1 = 0)，我如何计算 x )?例如:

0xcb9102df * x = 0x4d243a5d

在那种情况下，x 是 0x1908c643。我发现了一个类似的问题，但前提不同，我希望有一个比给出的解决方案更简单的解决方案。

Answer 1

数字具有模乘逆模 2 的幂，当且仅当它们是奇数。其他一切都是经过位移的奇数(即使是零，也可能是任何东西，所有位都被移出)。所以有几种情况:

给定a * x = b

• tzcnt(a) > tzcnt(b)无解
• tzcnt(a) <= tzcnt(b)可解，有 2^tzcnt(a) 解

对于奇数 a，第二种情况有 1 个解的特例, 即 x = inverse(a) * b

更一般地说，x = inverse(a >> tzcnt(a)) * (b >> tzcnt(a))是一个解决方案，因为你写 a作为(a >> tzcnt(a)) * (1 << tzcnt(a)) , 所以我们用它的逆抵消左边的因素，我们把右边的因素作为结果的一部分(无论如何都不能取消)然后乘以剩下的东西得到它直到b .显然，仍然只适用于第二种情况。如果需要，您可以通过为顶部 tzcnt(a) 填写所有可能性来枚举所有解决方案。位。

唯一剩下的就是求逆，你可能已经在其他答案中看到过它，不管它是什么，但为了完整起见，你可以按如下方式计算它:(未测试)

; input x
dword y = (x * x) + x - 1;
dword t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
; result y