找回密码
 欢迎注册
楼主: KeyTo9_Fans

[求助] 2个64bit的无符号整数相乘,C++如何实现最快?

[复制链接]
发表于 2020-5-13 11:10:03 | 显示全部楼层
如果使用在Linux下编程是可以直接使用128位整数类型的.
  1. #include <stdint.h>
  2. #include <stdio.h>
  3. #include <inttypes.h>

  4. typedef unsigned __int128 uint128_t;

  5. uint128_t mul64(uint64_t a, uint64_t b) {
  6.     return (uint128_t)a * b;
  7. }


  8. // 下面的print_u128_u 代码来自
  9. // https://stackoverflow.com/questions/11656241/how-to-print-uint128-t-number-using-gcc


  10. /*      UINT64_MAX 18446744073709551615ULL */
  11. #define P10_UINT64 10000000000000000000ULL   /* 19 zeroes */
  12. #define E10_UINT64 19

  13. #define STRINGIZER(x)   # x
  14. #define TO_STRING(x)    STRINGIZER(x)


  15. static int print_u128_u(uint128_t u128)
  16. {
  17.     int rc;
  18.     if (u128 > UINT64_MAX)
  19.     {
  20.         uint128_t leading  = u128 / P10_UINT64;
  21.         uint64_t  trailing = u128 % P10_UINT64;
  22.         rc = print_u128_u(leading);
  23.         rc += printf("%." TO_STRING(E10_UINT64) PRIu64, trailing);
  24.     }
  25.     else
  26.     {
  27.         uint64_t u64 = u128;
  28.         rc = printf("%" PRIu64, u64);
  29.     }
  30.     return rc;
  31. }


  32. int  main()
  33. {
  34.    uint128_t c;
  35.    uint64_t a=10000000000;
  36.    uint64_t b=10000000000;
  37.    c=mul64(a,b);
  38.    
  39.    int ndigits = print_u128_u(c);
  40.    printf("\n%d digits\n", ndigits);

  41.    return 0;
  42. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-6-16 10:36:22 | 显示全部楼层
还是rust好,原生支持128bit, 随便写一个有符号整数的乘法,是如此的优雅:
  1. fn main() {
  2.     let x:i128 = -1234567890123456789;
  3.     let y:i128 = 12345678901234567891;

  4.     println!("{ans}\n{ans:#0128b}", ans = x*y);
  5.     println!("{ans}\n{ans:#0128b}", ans = i128::MIN);
  6.     println!("{ans}\n{ans:#0128b}", ans = i128::MAX);
  7. }
复制代码

  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
复制代码

点评

来,要不要 一起玩。从此 不再担忧电脑的内存被撮爆了,只需要搞定编译通过就行  发表于 2020-6-17 16:52
rust大★好,退C包贫鞍  发表于 2020-6-17 15:20
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-12-29 10:50:43 | 显示全部楼层
好像使用__uint128_t类型,直接乘就行:
  1. #include<cstdio>
  2. __uint128_t a;

  3. int main()
  4. {
  5.         a=14757395258967641293;
  6.         a=a*14757395258967641293;
  7.         printf("%I64u %I64u\n",(unsigned long long)(a>>64),(unsigned long long)(a));
  8. }
  9. //运行结果:
  10. /*
  11. 11805916207174113034 10330176681277348905

  12. --------------------------------
  13. Process exited after 0.01809 seconds with return value 0
  14. */
复制代码
输出的时候:
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. int main()
  5. {
  6.         scanf("%I64u %I64u",&x,&y);
  7.         a=x;
  8.         a=a*y;
  9.         h=a>>64;
  10.         l=a;
  11.         printf("%I64u %I64u\n",h,l);
  12. }
复制代码
运行后输入:
18446744073709551615 18446744073709551615

就得到了这个输出:
18446744073709551614 1

--------------------------------
Process exited after 15.61 seconds with return value 0
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-11-24 11:44 , Processed in 0.103360 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表