How to Safely Average Two Unsigned Ints in C++

How can I safely average two unsigned ints in C++?

Your last approach seems promising. You can improve on that by manually considering the lowest bits of a and b:

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

This gives the correct results in case both a and b are odd.

Take the average of two signed numbers in C

Edit: version fixed by @chux - Reinstate Monica:

if ((a < 0) == (b < 0)) {  // a,b same sign
  return a/2 + b/2 + (a%2 + b%2)/2;
} else {
  return (a+b)/2;
}

Original answer (I'd have deleted it if it hadn't been accepted).

a/2 + b/2 + (a%2 + b%2)/2

Seems the simplest one fitting the bill of no assumption on implementation characteristics (it has a dependency on C99 which specifying the result of / as "truncated toward 0" while it was implementation dependent for C90).

It has the advantage of having no test (and thus no costly jumps) and all divisions/remainder are by 2 so the use of bit twiddling techniques by the compiler is possible.

Explanation of the safe average of two numbers

So let's consider bytes instead of ints. The only difference is that a byte is an 8-bit integer, while an int has 32 bits. In Java, both are always signed, meaning that the leading bit indicates whether they're positive (0) or negative (1).

byte low = Byte.valueOf("01111111", 2); // The maximum byte value
byte high = low; // This copies low.

byte sum = low + high; // The bit representation of this is 11111110, which, having a
                       // leading 1, is negative. Consider this the worst case
                       // overflow, since low and high can't be any larger.

byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow.

For ints, it's the same thing. Basically the gist of all this is that using an unsigned bitshift on signed integers allows you to leverage the leading bit to handle the largest possible values of low and high.

Fastest way to take the average of two signed integers in x86 assembly?

Depending on how we interpret your lax rounding requirements, the following may be acceptable:

sar rdi, 1
sar rsi, 1
adc rdi, rsi

Try on godbolt

This effectively divides both inputs by 2, adds the results, and adds 1 more if rsi was odd. (Remember that sar sets the carry flag according to the last bit shifted out.)

Since sar rounds to minus infinity, the result of this algorithm is:

exactly correct if rdi, rsi are both even or both odd
rounded down (toward minus infinity) if rdi is odd and rsi is even
rounded up (toward plus infinity) if rdi is even and rsi is odd

As a bonus, for random inputs, the average rounding error is zero.

It should be 3 uops on a typical CPU, with a latency of 2 cycles since the two sar are independent.

How to safely compare two unsigned integer counters?

I think you misinterpreted the comment in the code:

We divide by two to not overflow iter_c * 2.

No matter where the values are coming from, it is safe to write a/2 but it is not safe to write a*2. Whatever unsigned type you are using, you can always divide a number by two while multiplying may result in overflow.

If the condition would be written like this:

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

then roughly half of the input would cause a wrong condition. That being said, if you worry about counters overflowing, you could wrap them in a class:

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

Note that to avoid the overflow completely you have to take additional measures, but if a and b are increased more or less the same amount this might be fine already.

Efficient computation of the average of three unsigned integers (without overflow)

Let me throw my hat in the ring. Not doing anything too tricky here, I
think.

#include <stdint.h>

uint64_t average_of_three(uint64_t a, uint64_t b, uint64_t c) {
  uint64_t hi = (a >> 32) + (b >> 32) + (c >> 32);
  uint64_t lo = hi + (a & 0xffffffff) + (b & 0xffffffff) + (c & 0xffffffff);
  return 0x55555555 * hi + lo / 3;
}

Following discussion below about different splits, here's a version that saves a multiply at the expense of three bitwise-ANDs:

T hi = (a >> 2) + (b >> 2) + (c >> 2);
T lo = (a & 3) + (b & 3) + (c & 3);
avg = hi + (hi + lo) / 3;

How to subtract two unsigned ints with wrap around or overflow

Assuming two unsigned integers:

If you know that one is supposed to be "larger" than the other, just subtract. It will work provided you haven't wrapped around more than once (obviously, if you have, you won't be able to tell).
If you don't know that one is larger than the other, subtract and cast the result to a signed int of the same width. It will work provided the difference between the two is in the range of the signed int (if not, you won't be able to tell).

To clarify: the scenario described by the original poster seems to be confusing people, but is typical of monotonically increasing fixed-width counters, such as hardware tick counters, or sequence numbers in protocols. The counter goes (e.g. for 8 bits) 0xfc, 0xfd, 0xfe, 0xff, 0x00, 0x01, 0x02, 0x03 etc., and you know that of the two values x and y that you have, x comes later. If x==0x02 and y==0xfe, the calculation x-y (as an 8-bit result) will give the correct answer of 4, assuming that subtraction of two n-bit values wraps modulo 2ⁿ - which C99 guarantees for subtraction of unsigned values. (Note: the C standard does not guarantee this behaviour for subtraction of signed values.)