不使用 64 位 int 将两个 32 位数字相乘
我们正在使用以下算法进行一些 32 位 * 32 位乘法
让我们想要将 a（32 位）与 b（32 位）相乘，两者均带符号，
a = ah * 2^16 + al [ah - 高 16 位，al - 低 16 位]
b = bh * 2^16 + bl [bh - 高 16 位，bl - 低 16 位]
我们实际上正在做
Result = (al * bl) + (((ah * bl) + (al * bh)) * 2^16) + ((ah * bh) * 2 ^ 32) ~~~
我的问题，
他们有更好的方法吗？
We are doing some 32bit * 32bit multiplication using the following algorithm
Let us we want to multiply a (32 bit) with b (32 bit), both signed,
a = ah * 2^16 + al [ah - Higher 16 bits, al - Lower 16 bits]
b = bh * 2^16 + bl [bh - Higher 16 bits, bl - Lower 16 bits]
We are effectively doing
Result = (al * bl) + (((ah * bl) + (al * bh)) * 2^16) + ((ah * bh) * 2 ^ 32) ~~~
My question,
Is their any better way to do this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
在任何主流编译器中，在 32 位平台上模拟 64 位整数的效率与您自己进行多步数学运算一样高效。但它会更可靠地正确。
当使用大到足以溢出的值进行简单算术时，即使是我见过的最高度调整的数学库也只使用 int64。
In any mainstream compiler, the emulation of 64-bit ints on a 32-bit platform will be about as efficient as doing the mutli-step math yourself. But it will be much more reliably correct.
When doing simple arithmetic with values large enough to overflow, even the most highly tuned math library that I've seen just uses int64.
谷歌“Karatsuba乘法”。
OIh，在您的代码中，将常量 2^15（出现两次）更改为 2^16。
Google "Karatsuba multiplication".
OIh, and in your code, change the constant 2^15 (it appears twice) to 2^16.
答案是否定的，除了使用位移位和掩码而不是 2^n 之外，没有更好的方法了。即：
其次，你的整数是有符号的还是无符号的？如果他们签署了，那么事情就会改变。
第三，我不确定你的 2^15 是否正确。如果它至少是无符号的，您需要将位移位 16 位而不是 15 位。
最后，您必须注意低位 int 中的整数溢出。如果将低位 int 中的数字相加，导致溢出其容量，则需要正确递增高位 int。
The answer is no there isn't a better way of doing things, apart from using bit shifting and and masks instead of 2^n. Namely:
Secondly, are your ints signed or unsigned? If they're signed then that changes things.
Third, I'm not sure your 2^15 is right. If it's unsigned at least, you want to shift bits by 16 not 15.
Lastly, you have to watch out for integer overflow in the low order int. If you add together numbers in the low order int that overflow it's capacity you need to correctly increment the high order int.
您需要知道（指定）如何存储 64 位值 - 大概是一对 32 位值，可能是数组的两个元素，或者结构体的两个元素。您还需要考虑如何将符号信息存储在结果中。
从机械上讲，您可能希望将两个有符号值转换为无符号值，然后按照您显示的线路进行拆分和重新组装，小心确保低位 32 位值的进位在高位 32 位中得到正确管理价值。
根据您最初的设计决策，您可能还需要调整结果符号的表示，甚至可能需要调整所有其他位。
类似的注释适用于将两个 16 位数字相乘而没有任何 32 位结果，这曾经很重要，但大多数人不必担心。
You need to know (specify) how the 64-bit value is to be stored - presumably, it is a pair of 32-bit values, possibly two elements of an array, or two elements of a structure. You also need to consider how the sign information is going to be stored in the result.
Mechanically, you probably want to convert both signed values to unsigned, and then do the split and reassemble along the lines you showed, being careful to ensure that carries from the low order 32-bit value are managed properly in the high order 32-bit value.
Depending on your initial design decisions, you may also need to fettle the representation of the sign of the result, and maybe even all the other bits.
Similar comments apply to multiplying two 16-bit numbers without any 32-bit results, something that was once important but most people don't have to worry about.