c++stlsubtractioninteger-overflowunderflow

"Symmetrical difference" for unsigned ints - assumed rollover


I made a simple function that I called symmetricDelta() which calculates the delta between value and previous "symmetrically". What I mean by that is: consider a number-line from e.g. 0 to ULLONG_MAX, where you connected the left and right ends of the number-line... To determine a "symmetric" delta, assume the change is positive if value - previous is less than half of the span, otherwise assume the change is negative, and we wrapped-around the number-line.

See a simple version of this for uint64_ts below:

int64_t symmetricDelta(uint64_t value, uint64_t previous) {
    if (value-previous < (1ULL << 63)) {
        uint64_t result = value - previous;
        return result;
    } else {
        uint64_t negativeResult = previous - value;
        return -1 * negativeResult;
    }
}

Usage:

    uint64_t value = ULLONG_MAX;
    uint64_t previous = 0;

    // Result: -1, not UULONG_MAX
    cout << symmetricDelta(value, previous) << endl;

Demo: https://onlinegdb.com/BJ8FFZgrP

Other value examples, assume a uint8_t version for simplicity:

symmetricalDifference(1, 0) == 1
symmetricalDifference(0, 1) == -1
symmetricalDifference(0, 255) == 1
symmetricalDifference(255, 0) == -1
symmetricalDifference(227, 100) == 127
symmetricalDifference(228, 100) == -128

My question is: Is there an "official" name for what I'm calling "symmetrical subtraction"? This feels like the kind of thing that might already be implemented in the C++ STL, but I wouldn't even know what to search for...


Solution

  • Yes. The name is subtraction modulo 2^64. And it's identical to what your machine does with the instruction

    int64_t symmetricDelta(uint64_t value, uint64_t previous) {
        return (int64_t)(value-previous);
    }
    

    In C and C++, unsigned arithmetic is defined to wrap around, effectively joining the ends of the representable number range into a circle. This is the basis for the 2-complement representation of signed integers: Your CPU simply declares half the number circle to be interpreted negative. This part is the upper part in unsigned, with the -1 corresponding to the maximum representable unsigned integer. Simply because the 0 is next on the circle.

    Side note:
    This allows the CPU to use the exact same circuitry for signed and unsigned arithmetic. The CPU only provides an add instruction that is used irrespective of whether the numbers should be interpreted as signed or unsigned. This is true for addition, subtraction and multiplication, they all exist as sign-ignorant instructions. Only the division is implemented in a signed and an unsigned variant, as are the comparison instructions / the flag bits that the CPU provides.

    Side note 2:
    The above is not fully true, as modern CPUs implement saturating arithmetic as part of their vector units (AVX etc.). Because saturating arithmetic means clipping the result to the ends of the representable range instead of wrapping around, this clipping depends on where the circle of numbers is assumed to be broken. As such, saturating arithmetic instructions typically exist in signed and unsigned variants.

    End of the needless background rambling...

    So, when you subtract two numbers in unsigned representation, the result is the unsigned number of steps that you have to take to reach the minuend from the subtrahend. And by reinterpreting the result as a signed integer, you are interpreting a long route (that goes more than half around the circle) as the corresponding short route in the opposite direction.


    There is one pitfall: 1 << 63 is not representable. It is exactly on the opposite side of the number circle from the zero, and since its sign bit is set, it's interpreted as -(1 << 63). If you try to negate it, the bit pattern does not change one bit (just like -0 == 0), so your computer happily declares that - -(1 << 63) == -(1 << 63). This is probably not a problem to you, but it's better to be aware of this, because it might bite you.