c++ - 对大数进行加法运算

Question

有两个n位数字存储在两个字节数组(小端)中。

例如:40位数字可以表示为:char c[5] = {0xff, 0xff, 0xff, 0xff, 0x01} ;，则为0xffffffff01.

我的问题是如何在 C 或 C++ 中高效地实现两个 n 位数字的加运算？

其实我想实现对字节数组表示的大数的基本操作。有什么建议吗？

Answer 1

基本方法与您在小学时学到的方法相同。从最低有效字节开始，将两个字节与传入进位相加。如果有进位，则进位到下一组。

当然，今天的处理器不是 32 位就是 64 位，所以使用 uint32_t 更有意义或 uint64_t作为基本类型而不是 char .请注意，您可能希望未签名，而不是已签名。

您始终可以查看为此目的编写的库中的代码。 GMP 有一对“mini-gmp”.h/.c 文件，可实现最基本的操作。您可以在这里在线浏览它们:mini-gmp.h , mini-gmp.c .特别是，您感兴趣的函数是 mpz_add .谷歌发现example usage . mpz_add委托(delegate)给其他功能，但主要内容似乎是第 393 行的这个功能:

mp_limb_t
mpn_add_n (mp_ptr rp, mp_srcptr ap, mp_srcptr bp, mp_size_t n)
{
  mp_size_t i;
  mp_limb_t cy;

  for (i = 0, cy = 0; i < n; i++)
    {
      mp_limb_t a, b, r;
      a = ap[i]; b = bp[i];
      r = a + cy;
      cy = (r < cy);
      r += b;
      cy += (r < b);
      rp[i] = r;
    }
  return cy;
}

我会留给你来弄清楚类型的含义、内存分配的工作原理等，但想想一个 mp_limb_t作为你的char .