CODEWITHSUNDEEP
cintegerstandardsunderflow
Reinstate Monica
Reinstate Monica

Reputation: 628

Unsigned integer underflow in C

I've seen multiple questions on the site addressing unsigned integer overflow/underflow. Most of the questions about underflow ask about assigning a negative number to an unsigned integer; what's unclear to me is what happens when an unsigned int is subtracted from another unsigned int e.g. a - b where the result is negative. The relevant part of the standard is:

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.

In this context how do you interpret "reduced"? Does it mean that UINT_MAX+1 is added to the negative result until it is >= 0?

I see that the main point is addressed by this question (which basically says that the standard chooses to talk about overflow but the main point about modulo holds for underflow too) but it's still unclear to me:

Say the result of a-b is -1; According to the standard, the operation -1%(UINT_MAX+1) will return -1 (as is explained here); so we're back to where we started.

This may be overly pedantic, but does this modulo mean a mathematical modulo as opposed to C's computational modulo?

Upvotes: 3

Views: 5222

Answers (3)

William J Bagshaw
William J Bagshaw

Reputation: 565

Under the hood, addition, or subtraction is bit wise and sign independent. The code generated could use the same instructions independent of whether it is signed or not. It is other operators that interpret the result, for example a > 0. Do the bit wise add or sub and this tells you the answer. b0 - b1 = b111111111 the answer is the same independent of the sign. It is only other operators that see the answer as -1 for signed types and 0xFF for unsigned types. The standard describes this behaviour, but I always find it easiest to remember how it works and deduce the consequences to the code I am writing.

signed int adds(signed int a, signed int b)
{
    return a + b;
}

unsigned int addu(unsigned a, unsigned b)
{
    return a + b;
}


int main() {
    return 0;
}

-> 

adds(int, int):
  lea eax, [rdi+rsi]
  ret
addu(unsigned int, unsigned int):
  lea eax, [rdi+rsi]
  ret
main:
  xor eax, eax
  ret

Upvotes: 1

AnT stands with Russia
AnT stands with Russia

Reputation: 320481

Firstly, a result that is below the minimum value of the given integer type is not called "underflow" in C. The term "underflow" is reserved for floating-point types and means something completely different. Going out of range of an integer type is always overflow, regardless of which end of the range you cross. So the fact that you don't see the language specification talking about "underflow" doers not really mean anything in this case.

Secondly, you are absolutely right about the meaning of the word "reduced". The final value is defined by adding (or subtracting) UINT_MAX+1 from the "mathematical" result until it returns into the range of unsigned int. This is also the same thing as Euclidean "modulo" operation.

Upvotes: 6

Enzo Nakamura
Enzo Nakamura

Reputation: 137

The part of the standard you posted talks about overflow, not underflow.

"Does it mean that UINT_MAX+1 is added to the negative result until it is >= 0?"

You can think that's what happens. Abstractly the result will be the same. A similar question has already been asked about it. Check this link: Question about C behaviour for unsigned integer underflow for more details.

Another way to think is that, for example, -1 is in principle from type int (that is 4 bytes, in which all bits are 1). Then, when you tell the program to interpret all these bits 1 as unsigned int, its value will be interpreted as UINT_MAX.

Upvotes: 1

Related Questions