我试图乘两个uint64_t
s并将结果存储到uint64_t
。我在Stackoverflow上找到了一个现有的答案,它将输入拆分为四个uint32_t
s,并在稍后加入结果:
https://stackoverflow.com/a/28904636/1107474
我已经使用代码创建了一个完整的示例,并将其粘贴到下面。
然而,对于37 x 5
,我得到的结果是0
而不是185
?
#include <iostream>
int main()
{
uint64_t a = 37; // Input 1
uint64_t b = 5; // Input 2
uint64_t a_lo = (uint32_t)a;
uint64_t a_hi = a >> 32;
uint64_t b_lo = (uint32_t)b;
uint64_t b_hi = b >> 32;
uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = a_hi * b_lo;
uint64_t b_x_a_mid = b_hi * a_lo;
uint64_t a_x_b_lo = a_lo * b_lo;
uint64_t carry_bit = ((uint64_t)(uint32_t)a_x_b_mid +
(uint64_t)(uint32_t)b_x_a_mid +
(a_x_b_lo >> 32) ) >> 32;
uint64_t multhi = a_x_b_hi +
(a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
carry_bit;
std::cout << multhi << std::endl; // Outputs 0 instead of 185?
}
我正在将您的代码与原始链接中的另一个答案合并。
#include <iostream>
int main()
{
uint64_t a = 37; // Input 1
uint64_t b = 5; // Input 2
uint64_t a_lo = (uint32_t)a;
uint64_t a_hi = a >> 32;
uint64_t b_lo = (uint32_t)b;
uint64_t b_hi = b >> 32;
uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = a_hi * b_lo;
uint64_t b_x_a_mid = b_hi * a_lo;
uint64_t a_x_b_lo = a_lo * b_lo;
/*
This is implementing schoolbook multiplication:
x1 x0
X y1 y0
-------------
00 LOW PART
-------------
00
10 10 MIDDLE PART
+ 01
-------------
01
+ 11 11 HIGH PART
-------------
*/
// 64-bit product + two 32-bit values
uint64_t middle = a_x_b_mid + (a_x_b_lo >> 32) + uint32_t(b_x_a_mid);
// 64-bit product + two 32-bit values
uint64_t carry = a_x_b_hi + (middle >> 32) + (b_x_a_mid >> 32);
// Add LOW PART and lower half of MIDDLE PART
uint64_t result = (middle << 32) | uint32_t(a_x_b_lo);
std::cout << result << std::endl;
std::cout << carry << std::endl;
}
结果是
Program stdout
185
0
Godbolt链接:https://godbolt.org/z/97xhMvY53
或者你可以使用__uint128_t,这是非标准的,但广泛使用。
static inline void mul64(uint64_t a, uint64_t b, uint64_t& result, uint64_t& carry) {
__uint128_t va(a);
__uint128_t vb(b);
__uint128_t vr = va * vb;
result = uint64_t(vr);
carry = uint64_t(vr >> 64);
}
在这个问题的标题中,你说你想要将两个整数相乘。但是你在另一个Q&A上找到的代码(获取64位整数乘法的高位部分)并没有试图做到这一点,它只是试图获得的高位部分完整的产品。对于64x64 =>128位产品,高一半是product >> 64
。
-
37 x 5 = 185
-
185 >> 64 = 0
它正确地模拟了multihi = (37 * (unsigned __int128)5) >> 64
,而你忘记了>>64
部分。
__int128
是一个GNU C扩展;它比用纯ISO C手动模拟要有效得多,但目前的编译器只支持64位目标。看看我对同一个问题的回答。(ISO C23期望具有_BitInt(128)
或您指定的任何宽度)
在评论中你谈到了浮点尾号。在FP乘法中,您有两个n位尾数(通常设置其前导位),因此2n位乘积的高一半将具有n个有效位(或多或少;也许实际上是右边的一个位置(IIRC)。
像37 x 5这样的东西只会发生在微小的非正常浮动上,在那里乘积确实会下流到零。但在这种情况下,这可能是因为你只在指数范围的极限处得到次法线,(37 * 2^-1022) * (5 * 2^-1022)
将是186 * 2^-2044
,这个指数太小,无法用像IEEE binary64又名double
这样的FP格式表示,其中-1022
是最小指数。
您使用的是整数,其中a>>63
不是1
,实际上它们都小于2^32,因此在完整的128位乘积的低64位之外没有有效位。