How to subtract two unsigned ints with wrap around or overflow

user_211463 0
Viewed 50739

There are two unsigned ints (x and y) that need to be subtracted. x is always larger than y. However, both x and y can wrap around; for example, if they were both bytes, after 0xff comes 0x00. The problem case is if x wraps around, while y does not. Now x appears to be smaller than y. Luckily, x will not wrap around twice (only once is guaranteed). Assuming bytes, x has wrapped and is now 0x2, whereas y has not and is 0xFE. The right answer of x - y is supposed to be 0x4.

Maybe, 

( x > y) ? (x-y) : (x+0xff-y);

But I think there is another way, something involving 2s compliment?, and in this embedded system, x and y are the largest unsigned int types, so adding 0xff... is not possible

What is the best way to write the statement (target language is C)?

subtraction overflow int c
9 Answers

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 2n - which C99 guarantees for subtraction of unsigned values. (Note: the C standard does not guarantee this behaviour for subtraction of signed values.)

user_2428890

Maybe I don't understand, but what's wrong with:

unsigned r = x - y;

user_872340

The question, as stated, is confusing. You said that you are subtracting unsigned values. If x is always larger than y, as you said, then x - y cannot possibly wrap around or overflow. So you just do x - y (if that's what you need) and that's it.

user_1876900

To echo everyone else replying, if you just subtract the two and interpret the result as unsigned you'll be fine.

Unless you have an explicit counterexample.

Your example of x = 0x2, y= 0x14 would not result in 0x4, it would result in 0xEE, unless you have more constraints on the math that are unstated.

MSN_62100

Yet another answer, and hopefully easy to understand:

SUMMARY:

  • It's assumed the OP's x and y are assigned values from a counter, e.g., from a timer.
  • (x - y) will always give the value desired, even if the counter wraps.
  • This assumes the counter is incremented less than 2^N times between y and x, for N-bit unsigned int's.

DESCRIPTION:
A counter variable is unsigned and it can wrap around.
A uint8 counter would have values:
0, 1, 2, ..., 255, 0, 1, 2, ..., 255, ...

The number of counter tics between two points can be calculated as shown below.
This assumes the counter is incremented less than 256 times, between y and x.

uint8 x, y, counter, counterTics;
<initalize the counter>
<do stuff while the counter increments>
y = counter;
<do stuff while the counter increments>
x = counter;
counterTics = x - y;

EXPLANATION:
For uint8, and the counter-tics from y to x is less than 256 (i.e., less than 2^8):

If (x >= y) then: the counter did not wrap, counterTics == x - y

If (x < y) then: the counter wrapped, counterTics == (256-y) + x
(256-y) is the number of tics before wrapping.
x is the number of tics after wrapping.

Note: if those calculations are made in the order shown, no negative numbers are involved.

This equation holds for both cases: counterTics == (256+x-y) mod 256

For uintN, where N is the number of bits:
counterTics == ((2^N)+x-y) mod (2^N)

The last equation also describes the result in C when subtracting unsigned int's, in general.
This is not to say the compiler or processor uses that equation when subtracting unsigned int's.

RATIONALE:
The explanation is consistent with what is described in this ACM paper:
"Understanding Integer Overflow in C/C++", by Dietz, et al.

  1. HARDWARE INTEGER ARITHMETIC
    When an n-bit addition or subtraction operation on unsigned or two’s complement integers overflows, the result “wraps around,” effectively subtracting 2n from, or adding 2n to, the true mathematical result. Equivalently, the result can be considered to occupy n+1 bits; the lower n bits are placed into the result register and the highest-order bit is placed into the processor’s carry flag.

  2. INTEGER ARITHMETIC IN C AND C++
    3.3. Unsigned Overflow
    A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.
    Thus, the semantics for unsigned overflow in C/C++ are precisely the same as the semantics of processor-level unsigned overflow as described in Section 2. As shown in Table I, UINT MAX+1 must evaluate to zero in a conforming C and C++ implementation.

Also, it's easy to write a C program to test that the cases shown work as described.

user_154254470
Related