合理的便携方式来获得64×64位顶级64位乘法？ [英] Reasonably portable way to get top 64-bits from 64x64 bit multiply?

问题描述

有没有在C / C ++一个合理的可移植的方式将两个64位整数的128位结果，并获得的上方的结果的64位，而不是底部64位？我需要这个了一个多任意大小的表分发的哈希函数。

Is there a reasonably portable way in C/C++ to multiply two 64-bit integers for a 128-bit result and get the top 64-bits of the result, rather than the bottom 64-bits? I need this for distributing a hash function over an arbitrary sized table.

推荐答案

这个回答显示了如何从一个64×64位得到（精确）前64位乘法，不支持128位整数的系统上。通过@amdn答案将在该做的支持128位整数的系统提供更好的性能。

This answer shows how to get the (exact) top 64-bits from a 64x64 bit multiply on a system that doesn't support 128-bit integers. The answer by @amdn will give better performance on systems that do support 128-bit integers.

下图显示了用于从两个64位数字计算128位产品的一种方法。每个黑色矩形重新presents一个64位数字。 64位输入法， X 和是，分为标有32位块 A ， b ， C 和 D 。然后，四个32×32位的乘法被执行，给予4标记的64位产品 A * C ， B * C ， A * D 和 b * D 。这四个产品必须移位，并增加了用于计算最终的答案。

The diagram below shows one method for computing a 128-bit product from two 64-bit numbers. Each black rectangle represents a 64-bit number. The 64-bit inputs to the method, X and Y, are divided into 32-bits chunks labeled a, b, c, and d. Then four 32x32 bit multiplications are performed, giving four 64-bit products labeled a*c, b*c, a*d, and b*d. The four products must be shifted and added to compute the final answer.

需要注意的是128位产品的低32位仅由部分积 B * D 的低32位决定。下一个32位由以下的低32位来确定

Note that the lower 32-bits of the 128-bit product are solely determined by the lower 32-bits of partial product b*d. The next 32-bits are determined by the lower 32-bits of the following

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

注意 mid34 是3个32位数字的总和，因此事实上是一个34位的总和。的 mid34 充当扛高两位为64×64位的顶级64位乘法。

Note that mid34 is the sum of three 32-bit numbers and therefore is in fact a 34-bit sum. The upper two bits of mid34 act as a carry into the top 64-bits of the 64x64 bit multiply.

这给我们带来演示code。在 top64 函数计算64×64乘法的高64位。这是一个有点冗长，以允许低64位的计算在注释中显示。在主函数采用128位的整数优势来验证一个简单的测试案例的结果。进一步的测试是作为练习留给读者。

Which brings us to the demo code. The top64 function computes the upper 64-bits of a 64x64 multiply. It's a little verbose to allow for the calculation of the lower 64-bits to be shown in a comment. The main function takes advantage of 128-bit integers to verify the results with a simple test case. Further testing is left as an exercise for the reader.

#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 ) );
}

这篇关于合理的便携方式来获得64×64位顶级64位乘法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！