主页 / 问题 / 943320
Accepted
Никита Самоуков
Asked:2020-02-11 05:59:48 +0000 UTC2020-02-11 05:59:48 +0000 UTC

加减法溢出 C++

  • 772

您如何执行 + 并获得溢出？为此做某种条件构造很奇怪。处理器有一个溢出标志。

例如，一般情况下，您需要添加 2 个 2048 位的数字。

理论上这是一个addc命令，但是在c++中怎么做呢？

c++

1 个回答

  1. Best Answer

    C++ 中没有直接的等价物addc。要在纯 C++ 中执行长加法，您可以执行以下操作：

    1. 添加时使用最大整数类型作为数字。通过附加检查捕获溢出：如果总和小于一项（任何一项），则传输到下一位为 1。

      假设我们需要在 64 位平台上使用 256 位整数（最大整数类型是std::uint64_t）。那么这个选项可能看起来像这样

      using Number64 = std::uint64_t [4]; // 256 значащих бит

void add(const Number64 &lhs, const Number64 &rhs, Number64 &res)
{
  std::uint64_t c;
  res[0] = lhs[0] + rhs[0]; c = res[0] < lhs[0];
  res[1] = lhs[1] + rhs[1] + c; c = c ? res[1] <= lhs[1] : res[1] < lhs[1];
  res[2] = lhs[2] + rhs[2] + c; c = c ? res[2] <= lhs[2] : res[2] < lhs[2];
  res[3] = lhs[3] + rhs[3] + c;    
}

      顺便说一句，GCC 和 MSVC 都猜测adc在翻译此代码以执行加法本身时使用。但是他们没有考虑到这个adc和下一个转移已经产生的事实。

    2. 另外使用小于最大值（最大值的一半）的整数类型作为数字。要执行加法，请将数字转换为最大整数类型。在这种情况下，传输是明确获得的。

      在相同的条件下，这个选项可能看起来像这样

      using Number32 = std::uint32_t [8]; // 256 значащих бит

void add(const Number32 &lhs, const Number32 &rhs, Number32 &res)
{
  std::uint64_t c;
  res[0] = c = (std::uint64_t) lhs[0] + rhs[0]; 
  res[1] = c = (std::uint64_t) lhs[1] + rhs[1] + (c >> 32);
  res[2] = c = (std::uint64_t) lhs[2] + rhs[2] + (c >> 32);
  res[3] = c = (std::uint64_t) lhs[3] + rhs[3] + (c >> 32);
  res[4] = c = (std::uint64_t) lhs[4] + rhs[4] + (c >> 32);
  res[5] = c = (std::uint64_t) lhs[5] + rhs[5] + (c >> 32);
  res[6] = c = (std::uint64_t) lhs[6] + rhs[6] + (c >> 32);
  res[7] = (std::uint64_t) lhs[7] + rhs[7] + (c >> 32);
}

    3. 可以使第二个选项在加法运算中表现得不那么“浪费”：以最大整数类型存储位，但同时使每个位的最高有效位未使用。也就是说，例如，每个std::uint64_t字将仅存储 63 个有用位。并且每个高位都将未被使用：它被保留以便进位到达那里。同时，要表示一个 256 位的值，需要 5 个std::uint64_t字，而不是 4 个

      using Number63 = std::uint64_t [5]; // 320 бит, 315 значащих

void add(const Number63 &lhs, const Number63 &rhs, Number63 &res)
{
  res[0] = lhs[0] + rhs[0];
  res[1] = lhs[1] + rhs[1] + (res[0] >> 63); res[0] &= 0x7FFFFFFFFFFFFFFF;
  res[2] = lhs[2] + rhs[2] + (res[1] >> 63); res[1] &= 0x7FFFFFFFFFFFFFFF;
  res[3] = lhs[3] + rhs[3] + (res[2] >> 63); res[2] &= 0x7FFFFFFFFFFFFFFF;
  res[4] = lhs[4] + rhs[4] + (res[3] >> 63); res[3] &= 0x7FFFFFFFFFFFFFFF;
  res[4] &= 0x7FFFFFFFFFFFFFFF;
}

      但是我认为这种在位序列中带有“漏洞”的表示并没有多大意义。这也将使其他操作难以实施。

    只要只使用硬件平台本机支持的类型（即最高std::uint64_t64 位平台的类型），第一个选项似乎是最有效的。但是，如果编译器为扩展整数类型提供模拟支持（例如，__uint128_t64 位平台上的 GCC 支持）并且编译器擅长优化此类类型的操作，那么第二个选项将其__uint128_t用作“最大值”类型，可以和第一个竞争。

    • 1

相关问题