c - 处理大数和溢出

Question

我得到了一个包含 N 个元素的数组，我需要在这个数组中找到索引 P，其中 0 到 P 范围内的值的总和等于 P+1 到 N-1 范围内的值的总和。

数组中每个元素的值的范围可以是 -2147483648 到 2147483647，N 可以最大为 10000000。

鉴于此，如何确保在添加每个值以查找索引 P 时没有溢出？

Answer 1

为确保不溢出，请使用int32_tand int64_t。

值范围 [-2147483648 ... 2147483647] 与int32_t范围匹配。您也可以使用int64_t它，但是 10000000 的数组值得考虑空间。

由于任何10,000,000 个值的总和不超过 的范围int64_t，请使用 执行所有加法int64_t。

#include <stdint.h>
size_t foo(const int32_t *value, size_t N) {
  int64_t sum = 0;
  ...
  sum += value[i];
  ...
}

---

顺便说一句：相信可以有一个不需要添加 64 位添加的解决方案。
[编辑]未能得出简单的int32_t唯一解决方案，但想出了：

size_t HalfSum(const int32_t *value, size_t N) {
  // find sum of entire array    
  int64_t ArraySum = 0;
  size_t P;
  for (P = 0; P < N; P++) {
    ArraySum += value[P];
  }

  // compute sum again, stopping when it is half of total
  int64_t PartialSum = 0;
  for (P = 0; P < N; P++) {
    PartialSum += value[P];
    if ((PartialSum * 2) == ArraySum) {
      return P;
    }
  }

  return N;  // No solution (normally P should be 0 ... N-1)
}

Answer 2

使用 64 位整数进行计算。最好使用的类型是int64_t因为long不能保证是 64 位（您必须#include <stdint.h>使其可用）。

编辑：Pascal Cuoq 是对的：long long确实也提供 64 位保证并且不需要包含（但它可以长于 64 位），所以long如果你想成为，它只是你必须避免的类型便携的。

Answer 3

在最坏的情况下，P+1 = N-1。由于对于任何单个数字，ynumber 的最大值只能是 2147483647 或 -2147483647，这意味着在最坏的情况下，P 将是 long 的最大值或最小值。在其他情况下，P 仍然是一个长整数。因此，您只需要在最坏的情况下使用 long （因为如果您的最坏情况的预期结果是 P 是任何单个数字可以是 long 的最大可能数字。

为确保您不必使用更大的值，请将负值与正值配对，以使您保持在 long 的溢出以下。

假设我们有 3 个数字 ab 和 c。如果 a + b 溢出 long 数据类型，我们知道 c 不会是 P。

现在假设我们有 4 个数字，a, b, c, d 使得 a + b + c = d（意味着 d 是 P），如果 a + b 会溢出 long，这意味着 1）c 不能是 P 2）那里是 a + b + c 的组合，因此 long 的数据类型不需要溢出。

例如，a 是 max long，b 是 max long，c 是 min long，d 是 0，那么 a + c + b = d 将是正确的操作组合，以便不使用大于 long 的数据类型，我们可以尝试 a + c，因为我们知道 c 不可能是 P，因为 a + b 会溢出 long > P 的最大可能值。