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

liangbch

如果使用在Linux下编程是可以直接使用128位整数类型的.

1. #include <stdint.h>
   
2. #include <stdio.h>
   
3. #include <inttypes.h>
   
4. 
   
5. typedef unsigned __int128 uint128_t;
   
6. 
   
7. uint128_t mul64(uint64_t a, uint64_t b) {
   
8.     return (uint128_t)a * b;
   
9. }
   
10. 
    
11. 
    
12. // 下面的print_u128_u 代码来自
    
13. // https://stackoverflow.com/questions/11656241/how-to-print-uint128-t-number-using-gcc
    
14. 
    
15. 
    
16. /*      UINT64_MAX 18446744073709551615ULL */
    
17. #define P10_UINT64 10000000000000000000ULL   /* 19 zeroes */
    
18. #define E10_UINT64 19
    
19. 
    
20. #define STRINGIZER(x)   # x
    
21. #define TO_STRING(x)    STRINGIZER(x)
    
22. 
    
23. 
    
24. static int print_u128_u(uint128_t u128)
    
25. {
    
26.     int rc;
    
27.     if (u128 > UINT64_MAX)
    
28.     {
    
29.         uint128_t leading  = u128 / P10_UINT64;
    
30.         uint64_t  trailing = u128 % P10_UINT64;
    
31.         rc = print_u128_u(leading);
    
32.         rc += printf("%." TO_STRING(E10_UINT64) PRIu64, trailing);
    
33.     }
    
34.     else
    
35.     {
    
36.         uint64_t u64 = u128;
    
37.         rc = printf("%" PRIu64, u64);
    
38.     }
    
39.     return rc;
    
40. }
    
41. 
    
42. 
    
43. int  main()
    
44. {
    
45.    uint128_t c;
    
46.    uint64_t a=10000000000;
    
47.    uint64_t b=10000000000;
    
48.    c=mul64(a,b);
    
49.    
    
50.    int ndigits = print_u128_u(c);
    
51.    printf("\n%d digits\n", ndigits);
    
52. 
    
53.    return 0;
    
54. }

复制代码

wayne

还是rust好，原生支持128bit, 随便写一个有符号整数的乘法，是如此的优雅：

1. fn main() {
   
2.     let x:i128 = -1234567890123456789;
   
3.     let y:i128 = 12345678901234567891;
   
4. 
   
5.     println!("{ans}\n{ans:#0128b}", ans = x*y);
   
6.     println!("{ans}\n{ans:#0128b}", ans = i128::MIN);
   
7.     println!("{ans}\n{ans:#0128b}", ans = i128::MAX);
   
8. }
   

复制代码

1. (base) [wayne@manjaro rustc]$ rustc hello.rs
   
2. (base) [wayne@manjaro rustc]$ ./hello
   
3. -15241578753238836751425087877625361999
   
4. 0b11110100100010001001010000100110001101000001110010101111111010101010101101000100011011000101000000110000111101001100100110110001
   
5. -170141183460469231731687303715884105728
   
6. 0b10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
   
7. 170141183460469231731687303715884105727
   
8. 0b1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

复制代码

KeyTo9_Fans

好像使用__uint128_t类型，直接乘就行：

1. #include<cstdio>
   
2. __uint128_t a;
   
3. 
   
4. int main()
   
5. {
   
6.         a=14757395258967641293;
   
7.         a=a*14757395258967641293;
   
8.         printf("%I64u %I64u\n",(unsigned long long)(a>>64),(unsigned long long)(a));
   
9. }
   
10. //运行结果：
    
11. /*
    
12. 11805916207174113034 10330176681277348905
    
13. 
    
14. --------------------------------
    
15. Process exited after 0.01809 seconds with return value 0
    
16. */

复制代码

输出的时候：
1、先右移64位，然后转换成unsigned long long输出，就是高64位
2、直接转换成unsigned long long输出，就是低64位

如果要严格按照楼主的要求，读入2个64位无符号整数，然后输出它们的乘积，就这样写：

1. #include<cstdio>
   
2. __uint128_t a;
   
3. unsigned long long x,y,h,l;
   
4. 
   
5. int main()
   
6. {
   
7.         scanf("%I64u %I64u",&x,&y);
   
8.         a=x;
   
9.         a=a*y;
   
10.         h=a>>64;
    
11.         l=a;
    
12.         printf("%I64u %I64u\n",h,l);
    
13. }

复制代码

运行后输入：
18446744073709551615 18446744073709551615

就得到了这个输出：
18446744073709551614 1

--------------------------------
Process exited after 15.61 seconds with return value 0