用 C 计算 64x64 int 乘积的高 64 位

问题描述

我希望我的 C 函数能够有效地计算两个 64 位有符号整数的乘积的高 64 位.我知道如何在 x86-64 程序集中使用 imulq 并从 %rdx 中提取结果.但是我完全不知道如何用 C 编写它，更不用说哄编译器高效地完成它了.

I would like my C function to efficiently compute the high 64 bits of the product of two 64 bit signed ints. I know how to do this in x86-64 assembly, with imulq and pulling the result out of %rdx. But I'm at a loss for how to write this in C at all, let alone coax the compiler to do it efficiently.

有没有人对用 C 写这个有什么建议?这是性能敏感的，因此手动方法"(如俄罗斯农民或 bignum 库)已被淘汰.

Does anyone have any suggestions for writing this in C? This is performance sensitive, so "manual methods" (like Russian Peasant, or bignum libraries) are out.

我编写的这个愚蠢的内联汇编函数可以工作，并且大致是我所追求的代码生成器:

This dorky inline assembly function I wrote works and is roughly the codegen I'm after:

static long mull_hi(long inp1, long inp2) {
    long output = -1;
    __asm__("movq %[inp1], %%rax;"
            "imulq %[inp2];"
            "movq %%rdx, %[output];"
            : [output] "=r" (output)
            : [inp1] "r" (inp1), [inp2] "r" (inp2)
            :"%rax", "%rdx");
    return output;
}

推荐答案

如果您在 x86_64 上使用相对较新的 GCC:

If you're using a relatively recent GCC on x86_64:

int64_t mulHi(int64_t x, int64_t y) {
    return (int64_t)((__int128_t)x*y >> 64);
}

在 -O1 及更高版本，这将编译为您想要的:

At -O1 and higher, this compiles to what you want:

_mulHi:
0000000000000000    movq    %rsi,%rax
0000000000000003    imulq   %rdi
0000000000000006    movq    %rdx,%rax
0000000000000009    ret

我相信 clang 和 VC++ 也支持 __int128_t 类型，所以这也应该适用于这些平台，但通常需要注意的是自己尝试.

I believe that clang and VC++ also have support for the __int128_t type, so this should also work on those platforms, with the usual caveats about trying it yourself.

这篇关于用 C 计算 64x64 int 乘积的高 64 位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！