c++ - 如何安全地比较两个无符号整数计数器？

Question

我们有两个未签名的计数器，我们需要比较它们以检查是否存在一些错误情况:

uint32_t a, b;
// a increased in some conditions
// b increased in some conditions
if (a/2 > b) {
   perror("Error happened!");
   return -1;
}

问题是 a 和 b 总有一天会溢出。如果 a 溢出，它仍然可以。但是如果 b 溢出了，那就是误报了。如何让这张支票万无一失？

我知道制作 a 和 b uint64_t 会延迟这个误报。但仍然不能完全解决这个问题。

===============

让我澄清一点:计数器用于跟踪内存分配，这个问题在dmalloc/chunk.c中找到。 :

#if LOG_PNT_SEEN_COUNT
  /*
   * We divide by 2 here because realloc which returns the same
   * pointer will seen_c += 2.  However, it will never be more than
   * twice the iteration value.  We divide by two to not overflow
   * iter_c * 2.
   */
  if (slot_p->sa_seen_c / 2 > _dmalloc_iter_c) {
    dmalloc_errno = ERROR_SLOT_CORRUPT;
    return 0;
  }
#endif

Answer 1

我认为您误解了代码中的注释:

We divide by two to not overflow iter_c * 2.

无论值来自哪里，写成a/2是安全的，但写成a*2是不安全的。无论您使用什么无符号类型，您始终可以将数字除以二，而乘法可能会导致溢出。

如果条件写成这样:

if (slot_p->sa_seen_c > _dmalloc_iter_c * 2) {

然后大约一半的输入会导致错误的情况。也就是说，如果您担心计数器溢出，您可以将它们包装在一个类中:

class check {
    unsigned a = 0;
    unsigned b = 0;
    bool odd = true;
    void normalize() {
        auto m = std::min(a,b);
        a -= m;
        b -= m;
    }
public:
    void incr_a(){ 
        if (odd) ++a;
        odd = !odd;
        normalize();
    }
    void incr_b(){ 
        ++b;
        normalize();
    }
    bool check() const { return a > b;}
}

请注意，要完全避免溢出，您必须采取额外的措施，但如果 a 和 b 增加或多或少相同的数量，这可能已经很好了。