How to subtract two unsigned ints with wrap around or overflow
Solution 1
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.)
Solution 2
Here's a little more detail of why it 'just works' when you subtract the 'smaller' from the 'larger'.
A couple of things going into this…
1. In hardware, subtraction uses addition: The appropriate operand is simply negated before being added.
2. In two’s complement (which pretty much everything uses), an integer is negated by inverting all the bits then adding 1.
Hardware does this more efficiently than it sounds from the above description, but that’s the basic algorithm for subtraction (even when values are unsigned).
So, lets figure 2 – 250 using 8bit unsigned integers. In binary we have
0 0 0 0 0 0 1 0
- 1 1 1 1 1 0 1 0
We negate the operand being subtracted and then add. Recall that to negate we invert all the bits then add 1. After inverting the bits of the second operand we have
0 0 0 0 0 1 0 1
Then after adding 1 we have
0 0 0 0 0 1 1 0
Now we perform addition...
0 0 0 0 0 0 1 0
+ 0 0 0 0 0 1 1 0
= 0 0 0 0 1 0 0 0 = 8, which is the result we wanted from 2 - 250
Solution 3
Maybe I don't understand, but what's wrong with:
unsigned r = x - y;
Solution 4
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.
Solution 5
This is an efficient way to determine the amount of free space in a circular buffer or do sliding window flow control.
Use unsigned int
s for head
and tail
- increment them and let them wrap!
Buffer length has to be a power of 2.
free = ((head - tail) & size_mask)
, where size_mask
is 2^n-1 the buffer or window size.
Related videos on Youtube
mgag
Updated on July 09, 2022Comments
-
mgag almost 2 years
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)?
-
ThinkJet over 14 yearsWhat you except from this "best way" ? Please clarify your requirements ...
-
jamesdlin over 14 yearsWhat do you mean "both x and y can wrap around"? Do you mean that they might wrap around if cast from unsigned to signed types?
-
mgag over 14 yearsThe two ints are unsigned. 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 0x14. The right answer of x - y is supposed to be 0x4. ( x > y) ? (x-y) : (x+0xff-y); but I think there is another way, and in this embedded system, x and y are the largest unsigned int types, so adding 0xff... is not possible.
-
Alok Singhal over 14 yearsIf a signed integral value has "wrapped around" (overflown), all bets are off. If you're on a two's complement system, then you can still subtract them assign to an
unsigned
value, but it's not portable. Garbage in, garbage out. -
AnT stands with Russia over 14 yearsYour reformulated question still makes little sense. Value don't wrap around by themselves. Once you have
x
thatx
will not wrap anywhere until you start modifying it somehow. If you are modifying it, show us how. At this time there's no way to meaningfully figure out what "wrap around" you are talikng about. -
Rich almost 13 yearsAlok: Signed integer overflow is undefined behavior.
-
LihO over 11 yearsAlso worth to have a look at: Is unsigned integer subtraction defined behavior? :)
-
-
ThinkJet over 14 yearsIn case of bytes:
255 - ( - 10) = ?
-
jamesdlin over 14 years
x - y
can wrap around if you're using signed ints. -
GManNickG over 14 yearsHe said both were unsigned.
-
AnT stands with Russia over 14 years@jamesdlin: The subject of the question clearly and explicitly states that we are subtracting unsigned ints.
-
jamesdlin over 14 yearsOops, sorry. The content of the question itself said just "ints", but I forgot to pay attention to the title itself.
-
mgag over 14 yearsyeah that was a type - fixed now.
-
Stephen Canon over 14 yearsIf you're using an unsigned type in C, it is guaranteed to wrap around as described here, whether or not the system uses 2s complement (§6.2.5, paragraph 9: "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.")
-
caf over 14 yearsIt bears repeating that Stephen is completely correct. unsigned arithmetic is completely defined in C, based on the width of the unsigned type.
-
Alok Singhal over 14 years@Stephen: The OP changed the question, and initially his wording implied that he expected signed values to wrap around predictably. You are, of course, completely correct.
-
Matthew Slattery over 12 years@endolith: thanks for commenting on this old answer and prodding me into editing it. You and others here are quite right; at the time I answered this, I'd encountered the trick before, but wasn't aware of the guarantee in the standard that it always works for unsigned subtraction.
-
oosterwal almost 12 yearsIf you're willing to take a performance hit, you can allow any positive buffer length by using the modulus operator:
free = ((head - tail) % buf_len);
-
czz about 11 yearsCasting unsigned int to signed int is not safe. §6.3.1.3 Signed and unsigned integers: the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.
-
Idan over 10 years20 - 200 doesn't give 0 and that's what he meant