按位乘法来实现结果

Question

是否存在一组通用规则,通过乘以已知和未知数字来实现某个数字.例如假设x = 13且z = 9

有没有办法找到这样的

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

我不想将它们用作数学整数,而是用于比特.所以,我想保持z为int.显然,位表示中存在溢出,但我不确定如何在没有暴力的情况下找到z强制在32位机器中的所有值.我认为你的数字很小,是负数.

注意:这不是或者是一个新的赋值,因此您可以将x和y更改为任何内容,这些只是示例.

Answer 1

首先,找到模反元素的x(13)模2 ³².有几种方法可以做,很多人会推荐扩展的欧几里得算法,但对于这种情况来说并不是最简单的.有关更简单的算法,请参阅Hacker's Delight第10章(常数除以整数).

无论如何,一旦你知道的13模2的模反元素³²是0xc4ec4ec5,乘该数字将z得到y.

0xc4ec4ec5 * 9 = 0xec4ec4ed

所以y = 0xec4ec4ed,0xec4ec4ed * 13确实是9.

注意,如果x是偶数,则它没有反转.如果它"最多只是为了z"(也就是说,它具有多于或少于尾随的零z),则可以在分割出它们的最高共同功率2之后以这种方式解决它.