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

Question

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

Answer 1

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

下图显示了一种从两个64位数字计算128位乘积的方法.每个黑色矩形代表一个64位数字.64位输入到该方法中,X和Y被分成标记为32位的块a,b,c,和d.然后四个32×32位的乘法被执行,给予4个64位的产品标记a*c,b*c,a*d,和b*d.必须移动并添加四个产品以计算最终答案.

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

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

注意,它mid34是三个32位数的总和,因此实际上是34位和.高两位mid34用作进位到64x64位的前64位乘法.

这将我们带到演示代码.该top64函数计算64x64乘法的高64位.允许在注释中显示较低64位的计算有点冗长.该main函数利用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 ) );
}