主页 / coding / 问题 / 78970247
Accepted
Arnaud
Asked: 2024-09-10 23:35:20 +0800 CST

使用最大限制避免乘法期间无符号溢出 - 如何定义限制值？

  • 772

我需要递归计算树下由无符号整数表示的整数。每个节点都与一个整数值相关联，该整数值通过将其子节点的数字相乘而递归计算得出。每个叶子都有一个未计算的静态数字，每个数字都大于 0。

问题是频繁溢出。实际上，当结果很大时我并不感兴趣。如果我得到的结果只是告诉我值是 > 就没问题了SOME_BIG_VALUE（在这种情况下我不需要真实值）。

我的想法是使用值 0（否则永远不会使用）作为任何“高数字”的约定，并且

//when multiplying a and b each being <= SOME_BIG_VALUE, there is no overflow
unsigned c = a*b; 
// add a check 
if (c > SOME_BIG_VALUE)
   c = 0;

定义 SOME_BIG_VALUE 及其最高可能值以避免溢出的最干净的方法是什么？

我考虑使用以下定义：

#DEFINE SOME_BIG_VALUE unsigned(sqrt(UINT_MAX));

但它看上去有点脏，不是吗？

我知道在大多数情况下，无符号数用 32 位或 64 位表示，但我不确定这是否保证。如果是，我可以检查我们处于哪种配置中，并SOME_BIG_VALUE分别创建 2^16-1 或 2^32-1 的定义。

c

2 个回答

  1. Best Answer

    避免无符号溢出a * b

    UINT_MAX许多方法涉及寻找或的平方根UINT_MAX + 1。

    OP 的 sqrt 检验

    ((unsigned) sqrt(UINT_MAX))当以某种方式编码为仅评估一次时，这当然是合理的。

    // Somewhat convoluted.
#define SOME_BIG_VALUE ((unsigned) sqrt(UINT_MAX))
static unsigned big_value = 0;
if (big_value == 0) {
  big_value = SOME_BIG_VALUE;
}
if (a > big_value || b > big_value) {
  // Potential overflow
}

    更严谨的方法可以使用：

    #define SOME_BIG_VALUE ((unsigned) sqrt((UINT_MAX/2 + 1)*2.0) - 1)因此，sqrt()更可能是精确的，因为(UINT_MAX/2 + 1)*2.0是精确的浮点2的幂，中的值位数unsigned通常是偶数，甚至是弱质量，也sqrt()可以完全正确地获得2的偶数幂的根。

    位宽测试

    #define UINT_BITS (sizeof(unsigned)*CHAR_BITS)
#define SOME_BIG_VALUE ((1u << (UINT_BITS/2)) - 1)
if (a > SOME_BIG_VALUE || b > SOME_BIG_VALUE) {
  // Potential overflow
}

    有多种方法可以处理奇数 sizeof(unsigned)*CHAR_BITS或unsigned填充（见下文），但上述方法适用于常见的实现。

    位宽UINT_MAX（即使unsigned有填充）：

    // https://stackoverflow.com/a/4589384/2410359  
/* Number of value bits in inttype_MAX, or in any (1<<k)-1 where 0 <= k < 2040 */  
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
// Value bit width of UINT_MAX (handles padded types).
#define UINT_BITS IMAX_BITS(UINT_MAX)

    C2X 具有UINT_WIDTH值位宽度。

    运行时检查

    if (a > 0 && b > UINT_MAX/a) {
  // a * b will overflow.
}

    更广泛的数学

    #if ULLONG_MAX/UINT_MAX > UINT_MAX
  unsigned long long prod = a;
  prod *= b;
  if (prod > UINT_MAX) {
    // Overflow
    • 1

  2. 如果您的编译器支持内置溢出检查，您应该使用它：__builtin_umul_overflow在GCC和Clang中；检查其他编译器的文档。

    unsigned c; 
if (__builtin_umul_overflow(a, b, &c)) {
    c = 0;
}
    • 0

相关问题