C:处理大数字时避免溢出

Question

我在C中实现了一些排序算法(排序整数),小心地uint64_t用来存储与数据大小有关的任何东西(因此也是计数器和东西),因为算法也应该用几千兆的数据集进行测试整数.

算法应该没问题,并且分配的数据量应该没有问题:数据存储在文件中,我们每次只加载很少的块,即使我们将内存缓冲区扼流到任何大小,一切也能正常工作.

使用高达4千兆字节的数据集进行测试(因此16GB的数据)工作正常(分类4Gint需要2228秒,约37分钟),但是当我们超过那个(即:8 Gints)时算法似乎没有停止(它是现在已经跑了大约16个小时).

我担心问题可能是由于整数溢出,也许循环中的计数器存储在32位变量上,或者我们可能正在调用一些与32位整数一起工作的函数.
还有什么呢？

有没有简单的方法来检查运行时是否发生整数溢出？

Answer 1

这是特定于编译器的,但如果您正在使用gcc,则可以编译-ftrapv以SIGABRT在发生有符号整数溢出时发出.

例如:

/* compile with gcc -ftrapv <filename> */
#include <signal.h>
#include <stdio.h>
#include <limits.h>

void signalHandler(int sig) {
  printf("Overflow detected\n");
}

int main() {
  signal(SIGABRT, &signalHandler);

  int largeInt = INT_MAX;
  int normalInt = 42;
  int overflowInt = largeInt + normalInt;  /* should cause overflow */

  /* if compiling with -ftrapv, we shouldn't get here */
  return 0;
}

当我在本地运行此代码时,输​​出是

Overflow detected
Aborted

Answer 2

看看-ftrapv和-fwrapv:

-ftrapv

此选项为加法,减法,乘法运算的带符号溢出生成陷阱.

-fwrapv

此选项指示编译器假设加法,减法和乘法的带符号算术溢出使用二进制补码表示.此标志启用一些优化并禁用其他优化.默认情况下,Java前端根据Java语言规范的要求启用此选项.

另请参见C:标准和编译器中的整数溢出,以及C的有用GCC标志.