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

KeyTo9_Fans

我想编写一个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
===============

程序运行时间越短越好。

请问如何实现？

gxqcn

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

KeyTo9_Fans

“如果在64位OS中，直接乘即可” 我知道直接乘可以得到低$64$位的$l$，高$64$位的$h$也可以直接乘得到吗？

gxqcn

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

KeyTo9_Fans

在ubuntu系统，g++语言里面， 两个$64$bit的整数相乘，要得到一个$128$bit的整数，用什么指令？ 网上只能找到两个$32$bit的整数相乘得到一个$64$bit的整数的指令。

mathe

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

gxqcn

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

KeyTo9_Fans

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

1. void m64(unsigned __int64 a,unsigned __int64 b)
2. {
3. unsigned __int64 ah,al,bh,bl,m;
4. ah=unsigned int(a>>32);
5. al=unsigned int(a);
6. bh=unsigned int(b>>32);
7. bl=unsigned int(b);
8. l=ah*bl;
9. m=al*bh;
10. h=ah*bh+(l>>32)+(m>>32);
11. l<<=32;
12. m=(m<<32)+l;
13. if(m<l)h++;
14. l=al*bl+m;
15. if(l<m)h++;
16. }

复制代码

其中，$l$和$h$是全局的无符号$64$位整数，是最终的结果。 不知道这段代码还有没有优化的余地。

gxqcn

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

1. void m64(unsigned __int64 a,unsigned __int64 b)
2. {
3. unsigned __int64 ah,al,bh,bl;
4. unsigned __int64 l,m,h;
6. ah=unsigned int(a>>32);
7. al=unsigned int(a);
8. bh=unsigned int(b>>32);
9. bl=unsigned int(b);
11. l=ah*bl;
12. m=al*bh+l;
13. h=((m<l)?(1ULL<<32):0)+ah*bh+(m>>32);
14. m<<=32;
15. l=al*bl+m;
16. if(l<m)++h;
17. }

复制代码

gxqcn

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