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)
}