从64×64位乘法获得最高64位的合理便携方式?

在C / C ++中是否有一个合理的可移植方式来为128位结果乘以两个64位整数并获得结果的 64位而不是底部的64位? 我需要这个来在任意大小的表上分配哈希函数。

这个答案显示了如何在不支持128位整数的系统上从64×64位乘法得到(精确)前64位。 @amdn的答案将在支持128位整数的系统上提供更好的性能。

下图显示了一种从两个64位数字计算128位乘积的方法。 每个黑色矩形代表一个64位数字。 方法的64位输入XY被分成标记为abcd 32位块。 然后执行四次32×32位乘法,得到四个标记为a*cb*ca*db*d 64位乘积。 必须移动并添加四个产品以计算最终答案。

在此处输入图像描述

请注意,128位乘积的低32位仅由部分乘积b*d的低32位决定。 接下来的32位由以下的低32位决定

 mid34 = ((b*c) & 0xffffffff) + ((a*d) & 0xffffffff) + ((b*d) >> 32); 

请注意, mid34是三个32位数的总和,因此实际上是34位和。 mid34的高两位充当64×64位乘法的前64位的进位。

这将我们带到演示代码。 top64函数计算64×64乘法的高64位。 允许在注释中显示较低64位的计算有点冗长。 main函数利用128位整数通过简单的测试用例validation结果。 进一步的测试留给读者练习。

 #include  #include  typedef unsigned __int128 uint128_t; uint64_t top64( uint64_t x, uint64_t y ) { uint64_t a = x >> 32, b = x & 0xffffffff; uint64_t c = y >> 32, d = y & 0xffffffff; uint64_t ac = a * c; uint64_t bc = b * c; uint64_t ad = a * d; uint64_t bd = b * d; uint64_t mid34 = (bd >> 32) + (bc & 0xffffffff) + (ad & 0xffffffff); uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32); // uint64_t lower64 = (mid34 << 32) | (bd & 0xffffffff); return upper64; } int main( void ) { uint64_t x = 0x0000000100000003; uint64_t y = 0x55555555ffffffff; uint128_t m = x, n = y; uint128_t p = m * n; uint64_t top = p >> 64; printf( "%016llx %016llx\n", top, top64( x, y ) ); } 

一个小代数永远不会伤害:

 #include  uint64_t top64(uint64_t x, uint64_t y) { uint64_t a = x >> 32, b = x & 0xFFFFFFFF; uint64_t c = y >> 32, d = y & 0xFFFFFFFF; return a * c + ((b * d >> 32) + (a * d) + (b * c)) >> 32 + ((((a * d) & 0xFFFFFFFF) + ((b *c) & 0xFFFFFFFF) + ((b * d) >> 32)) >> 32); } 

gcc和clang都支持128位整数作为扩展。

这是演示的一种方法

 #include  #include  //https://gcc.gnu.org/onlinedocs/gcc-4.8.1/gcc/_005f_005fint128.html#_005f_005fint128 using u128 = unsigned __int128; using u64 = uint64_t; void mul64x64( u64 a, u64 b, u64 & hi, u64 & lo ) { u128 product = u128(a) * b; lo = product; hi = product >> 64; } int main() { u64 hi, lo; mul64x64( 40282220, u64{1} << 63, hi, lo ); std::cout << hi << std::endl; } 

输出是

 set -x ; clang++ -std=c++11 -O0 -Wall -Werror main.cpp && ./a.out + clang++ -std=c++11 -O0 -Wall -Werror main.cpp + ./a.out 20141110