How to Compute an Unsigned Integer Average Without Overflow

Computing the average of two unsigned integers seems trivial, but the straightforward implementation return (a + b) / 2; can overflow when both operands are near the maximum 32‑bit value, yielding an incorrect result such as average(0x80000000U, 0x80000000U) == 0.

Method 1 – Subtract‑first reduces the operand size before division. If the larger operand is known, the function can be written as:

unsigned average(unsigned low, unsigned high) {
    return low + (high - low) / 2;
}

Method 2 – Divide‑each‑operand and fix the low bit avoids overflow by dividing both numbers first and then adding the carry bit:

unsigned average(unsigned a, unsigned b) {
    return (a / 2) + (b / 2) + (a & b & 1);
}

This technique was patented in 2016 (the patent has now expired).

Method 3 – SWAR (SIMD Within A Register) uses bitwise operations to combine the high and low parts:

unsigned average(unsigned a, unsigned b) {
    return (a & b) + ((a ^ b) / 2); // variant: (a ^ b) + (a & b) * 2
}

C++20 also provides std::midpoint for this purpose.

Method 4 – Cast to a wider type leverages a 64‑bit accumulator when the target architecture supports it:

unsigned average(unsigned a, unsigned b) {
    // Assume "unsigned" is 32‑bit and "unsigned long long" is 64‑bit.
    return ((unsigned long long)a + b) / 2;
}

When using a 64‑bit register, the lower 32 bits must be zero‑extended to avoid contaminating the result. On x86‑64 and AArch64 this happens automatically; on Alpha AXP or MIPS64 the values are sign‑extended, requiring extra instructions to clear the upper bits.

Method 5 – Carry‑rotate right (RCR) keeps the overflow bit by rotating the sum through the carry flag. The algorithm works on any n‑bit register where the sum is effectively n+1 bits:

// x86‑32
mov eax, a
add eax, b          ; overflow goes into carry
rcr eax, 1          ; rotate right through carry

// x86‑64
mov rax, a
add rax, b
rcr rax, 1

// ARM Thumb‑2 (clang)
movs r2, #0
adds r0, r0, r1
adcs r2, r2
lsrs r0, r0, #1
lsls r1, r2, #31
adds r0, r1, r0

If the processor lacks an RCR instruction, compiler intrinsics or built‑ins can emulate the same effect:

#if defined(_MSC_VER)
    unsigned sum;
    auto carry = _addcarry_u32(0, a, b, &sum);
    sum = (sum & ~1) | carry;
    return _rotr(sum, 1);
#elif defined(__clang__)
    unsigned carry;
    unsigned sum = __builtin_addc(a, b, 0, &carry);
    return __builtin_rotateright32(sum, 1);
#else
    #error Unsupported compiler.
#endif

Benchmarks show that code generation differs across compilers: MSC‑ver produces slightly larger code, while clang on ARM‑Thumb2 generates more efficient instructions.

The discussion originates from Raymond Chen’s blog post on the Old New Thing, which sparked extensive community analysis and additional variants, including the classic (a & b) + ((a ^ b) / 2) formulation and a 36‑instruction MIPS assembly version.

In summary, safely averaging two unsigned integers requires either reducing operand size before addition, using bitwise tricks to preserve the carry, casting to a wider type, or employing hardware‑specific rotate‑through‑carry instructions; the best choice depends on the target architecture and compiler support.