获得 64 位整数乘法的高位

本文介绍了获得 64 位整数乘法的高位的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在 C++ 中，说:

uint64_t i; uint64_t j;

then i * j 将产生一个 uint64_t，其值是 i 和 j，即 (i * j) mod 2^64.现在，如果我想要乘法的较高部分怎么办?我知道在使用 32 位整数时，有一个汇编指令可以做类似的事情，但我对汇编根本不熟悉，所以我希望得到帮助.

then i * j will yield an uint64_t that has as value the lower part of the multiplication between i and j, i.e., (i * j) mod 2^64. Now, what if I wanted the higher part of the multiplication? I know that there exists an assembly instruction do to something like that when using 32 bit integers, but I am not familiar at all with assembly, so I was hoping for help.

制作类似东西的最有效方法是什么:

What is the most efficient way to make something like:

uint64_t k = mulhi(i, j);

推荐答案

如果您使用的是 gcc 并且您的版本支持 128 位数字(尝试使用 __uint128_t)然后执行 128 乘法并提取高 64 位是可能的成为获得结果的最有效方式.

If you're using gcc and the version you have supports 128 bit numbers (try using __uint128_t) then performing the 128 multiply and extracting the upper 64 bits is likely to be the most efficient way of getting the result.

如果您的编译器不支持 128 位数字，那么 Yakk 的答案是正确的.但是，对于一般消费而言，它可能过于简短.特别是，实际实现必须小心溢出 64 位整数.

If your compiler doesn't support 128 bit numbers, then Yakk's answer is correct. However, it may be too brief for general consumption. In particular, an actual implementation has to be careful of overflowing 64 bit integers.

他提出的简单便携的解决方案是将 a 和 b 中的每一个分解为 2 个 32 位数字，然后使用 64 位乘法运算将这些 32 位数字相乘.如果我们写:

The simple and portable solution he proposes is to break each of a and b into 2 32-bit numbers and then multiply those 32 bit numbers using the 64 bit multiply operation. If we write:

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;

那么很明显:

a = (a_hi << 32) + a_lo; b = (b_hi << 32) + b_lo;

和:

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo) = ((a_hi * b_hi) << 64) + ((a_hi * b_lo) << 32) + ((b_hi * a_lo) << 32) + a_lo * b_lo

前提是使用 128 位(或更高)算法执行计算.

provided the calculation is performed using 128 bit (or greater) arithmetic.

但是这个问题需要我们用64位算法来完成所有的计算，所以我们不得不担心溢出.

But this problem requires that we perform all the calculcations using 64 bit arithmetic, so we have to worry about overflow.

由于 a_hi、a_lo、b_hi 和 b_lo 都是无符号 32 位数字，因此它们的乘积将适合无符号 64 位数字而不会溢出.但是，上面计算的中间结果不会.

Since a_ a_lo, b_ and b_lo are all unsigned 32 bit numbers, their product will fit in an unsigned 64 bit number without overflow. However, the intermediate results of the above calculation will not.

当数学必须以 2^64 为模数时，以下代码将实现 mulhi(a, b):

The following code will implement mulhi(a, b) when the mathemetics must be performed modulo 2^64:

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; return multhi;

正如 Yakk 所指出的，如果您不介意在高 64 位中偏离 +1，您可以省略进位位的计算.

As Yakk points out, if you don't mind being off by +1 in the upper 64 bits, you can omit the calculation of the carry bit.