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

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

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

我们除以2不溢出iter_c * 2.

无论值来自哪里,写入都是安全的,a/2但写入并不安全a*2.无论您使用的是哪种无符号类型,都可以将数字除以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增加或多或少相同的数量,这可能已经很好了.