参见英文答案 >
How can I multiply 64 bit operands and get 128 bit result portably?2个
在C/C++中有一个合理的可移植方式来为128位结果乘以两个64位整数并得到结果的前64位而不是底部的64位吗？我需要这个来在任意大小的表上分配哈希函数.
在C/C++中有一个合理的可移植方式来为128位结果乘以两个64位整数并得到结果的前64位而不是底部的64位吗？我需要这个来在任意大小的表上分配哈希函数.
解决方法
这个答案显示了如何在不支持128位整数的系统上从64×64位乘法获得(精确)前64位. @amdn的答案将在支持128位整数的系统上提供更好的性能.
下图显示了一种从两个64位数字计算128位乘积的方法.每个黑色矩形代表一个64位数字.方法的64位输入X和Y被分成标记为a,b,c和d的32位块.然后执行四次32×32位乘法,得到四个标记为a * c,b * c,a * d和b * 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位的计算有点冗长.主函数利用128位整数通过简单的测试用例验证结果.进一步的测试留给读者练习.
#include <stdio.h> #include <stdint.h> 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 ) ); }
