c - 处理大量和溢出

Question

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

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

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

Answer 1

为确保不溢出，请使用 int32_t 和 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)
}