2个64bit的无符号整数相乘，C++如何实现最快？

/相

我想编写一个C++程序，

输入两个$64$bit的整数$a$和$b$，

然后计算$a$*$b$，结果为$128$bit的整数，

我希望用两个$64$bit的整数$h$和$l$表示这个$128$bit的整数，

其中$h$为前$64$个bit，$l$为后$64$个bit。

最后输出$h$和$l$。

例$1$：
===============
输入：
4294967297        4294967297
——————————
输出：
1        8589934593
===============

例$2$：
===============
输入：
18446744073709551615        18446744073709551615
——————————
输出：
18446744073709551614        1
===============

程序运行时间越短越好。

请问如何实现？

_only

如果在64位OS中，直接乘即可；
如果在32位OS中，就比较麻烦了，要经历多次乘法，带位加法。
而乘法应尽量设计成并行的，指令集需用到SSE2，寄存器用到MM或XMM.

edzugxoggixo

“如果在64位OS中，直接乘即可”

我知道直接乘可以得到低$64$位的$l$，高$64$位的$h$也可以直接乘得到吗？

kutnfeuwunaxo

要用汇编，读取 RDX:RAX，其中 h <--RDX, l <-- RAX

Geraldufas

在ubuntu系统，g++语言里面，

两个$64$bit的整数相乘，要得到一个$128$bit的整数，用什么指令？

网上只能找到两个$32$bit的整数相乘得到一个$64$bit的整数的指令。

Charlslots

c++里面好像不支持内嵌的64位指令

efaugko

这个是不是与编译器是否支持相关？
好像记得是ICC支持的。
可惜现在我还没用过64位系统，没得试。

BristSes

由于不知道$64$位直接乘如何实现，先暂时用多次$32$位乘法来实现。代码如下：

1. void m64(unsigned __int64 a,unsigned __int64 b){        unsigned __int64 ah,al,bh,bl,m;        ah=unsigned int(a>>32);        al=unsigned int(a);        bh=unsigned int(b>>32);        bl=unsigned int(b);        l=ah*bl;        m=al*bh;        h=ah*bh+(l>>32)+(m>>32);        l<<=32;        m=(m<<32)+l;        if(m<l)h++;        l=al*bl+m;        if(l<m)h++;}

复制代码

其中，$l$和$h$是全局的无符号$64$位整数，是最终的结果。

不知道这段代码还有没有优化的余地。

Jeninslots

依葫芦画瓢，不知是否算更简洁些？

1. void m64(unsigned __int64 a,unsigned __int64 b){        unsigned __int64 ah,al,bh,bl;        unsigned __int64 l,m,h;        ah=unsigned int(a>>32);        al=unsigned int(a);        bh=unsigned int(b>>32);        bl=unsigned int(b);        l=ah*bl;        m=al*bh+l;        h=((m<l)?(1ULL<<32):0)+ah*bh+(m>>32);        m<<=32;        l=al*bl+m;        if(l<m)++h;}

复制代码

Geraldufas

特别注意：当 al*bh+ah*bl 溢出时，向 h 需加 2^32，而不是 1.
我是突然间发现并修正这个bug的。
（——再看楼主发给我的短消息，也指明了这点；可怜我刚才改了几遍，居然都仅+1）