Overflow in unsigned arithmetic in C

This came up in work recently – and I got a bit confused about it, so I thought it was worth writing it down in case someone like me needs to look it up.

Let’s consider a real world example – we have a 16 bit counter that increments on every event X and which we sample periodically: at our last sampling was at value 0xFFFD and at our current sample is 0x03. How many incidents of X have occurred?

Ignoring the possibility of a ‘double rollover’ or anything similar, the answer is 6 (don’t forget the counter goes through 0). But how can we calculate this programmatically?

It turns out it’s very simple and this always works:

uint16_t numberEvents = currentSample - previousSample

In C the calculation (constrained to 16 bits) of 0x03 – 0xFFFD with unsigned arithmetic results in an overflow (we cannot calculate a negative number) but the language standard gives us a well-defined answer that works well.

The answer of -65530 is reinterpreted as modulo 0x10000 (65536) and this comes out at 6. To explain why think of a smaller number system – modulo 5 say. Then the number line (integers and integers mod 5) looks like this:

Integers: 10 9 8 7 6 5 4 3 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10
Modulo 5: 0 4 3 2 1 0 4 3 2 1 0 4 3 2 1 0 4 3 2 1 0

Under this system we can see that 1 – 4 = -3 for integers but 2 mod 5 – which if this was a simple two bit counter would be the correct number of increments that had taken place.

2 thoughts on “Overflow in unsigned arithmetic in C

Comments are closed.