4

My platform is x86_64, and assume there are 3 variables whose types are all uint16_t:

uint16_t a, b, c;

And for the following two code snippets:
(1)

uint16_t tmp = b - a;
uint16_t result1 = c - tmp;

and (2):

uint16_t result2 = c - (b - a);

For code snippet (1), the tmp value can be overflow result of b - a, also result1 value can be another overflow result of c - tmp.
For code snippet (2), if I understand correctly, for c - (b - a), a, b and c will all be promoted to integer first, so only c - (b - a) can be overflow when assigned to result2.

I wrote a small program to test whether the code snippet (1) is equivalent to (2):

#include <inttypes.h>
#include <stdio.h>

int main(void) {
    uint16_t a, b, c;
    for (a = 1; a <= 3; a++) {
        for (b = 1; b <= 3; b++) {
            for (c = 1; c <=3; c++) {
                uint16_t tmp = b - a;
                uint16_t result1 = c - tmp;
                uint16_t result2 = c - (b - a);
                if (result1 != result2) {
                    printf("error\n");
                }
            }
        }
    }
}

And the test result shows me the code snippet (1) is equivalent to (2). But I can't understand the mathematical rationale behind it, anyone can give an explanation of it?

Improve this question
4
  • 4
    If a1 is congruent to a2 modulo p (in this case 2^16), and b1 is congruent to b2 modulo p, then a1+b1 is congruent to a2+b2 modulo p, and a1-b1 is congruent to a2-b2 modulo p. Commented Apr 10 at 8:05
  • 2
    As long as intermediate results are correct in some modulus of 2^bitwidthofresult, then you'll get the same answer. x = y mod ab => x = y mod a. Commented Apr 10 at 8:19
  • @SimonGoater Sorry, from your comment, what is the meaning of "x = y mod ab => x = y mod a"? Thanks! Commented Apr 11 at 0:45
  • y mod z is the remainder after integer division of y by z. I used x = y mod z to mean x and y have the same remainder after integer division by z. I used = because the proper symbol with three lines for 'is congruent to' isn't available. '=>' means 'implies'. So restated, if x,y,a,b are positive integers, then if x = y mod ab you know that in particular, x = y mod a. Commented Apr 11 at 8:00

3 Answers 3

Reset to default
5

Assuming a mainstream computer with 32 bit int and 2's complement, then:

Any b - a where both operands are uint16_t cannot overflow or underflow, since both operands are implicitly promoted to int and then underflow happens below -231 and overflow above 231-1. Since both operands are originally unsigned, their values must be positive. Meaning that the smallest number that can be achieved by b - a is -216+1 -65535. This value fits just fine in the promoted int so there is no underflow.

Upon storing -65535 back into a uint16_t, a well-defined signed to unsigned conversion happensa) and we end up with the number 1. There are no overflows or underflows - such can only happen during signed arithmetic.

Similarly if you skip the step of converting to a temporary uint16_t then the whole calculation c - (b - a) is carried out on int. Here too it is possible to reach a result which can't fit inside a uint16_t, but it doesn't matter since the conversion from int to uint16_t is still well-defined.

a) From C23 6.3.2.3:

Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

The rules describe arithmetic on the mathematical value, not the value of a given type of expression.

For example -65535 + (65535+1) = 1. This is in range of uint16_t so the new value is 1.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

why should the uint16_t vars be converted to int vars first? In my programming experience, everytime, an arithmetic operation that exceeds the originial type interval will eventually overflow in the result.
@WolfgangRoth Because that's how C works and always worked... All small integer types whenever part of most expressions, get implicitly promoted to int due to integer promotion and/or "the usual arithmetic conversions". For example the additive operators like - specifies: "If both operands have arithmetic type, the usual arithmetic conversions are performed on them." So it is literally impossible in C to carry out addition/subtraction on a small integer type like uint16_t.
@WolfgangRoth: The C standard specifies the usual arithmetic conversions are applied to the operands of binary - (and most arithmetic operators). When int is 32 bits, those conversions convert uint16_t to int.
4

If int is 16 bits, the narrowest the C standard allows, then uint16_t is not promoted to int, all arithmetic in the code in the question is done in uint16_t, so it wraps modulo 216, and there is no overflow. (In the terminology of the C standard, unsigned arithmetic never overflows; it is defined to wrap.)

If int is 17 bits, there is no overflow in int arithmetic with the small values used in the question. When a negative result is converted back to uint16_t, it wraps. If we had a = 65535, b = 0, and c = 65535, then c - (b - a) would mathematically be 131,070, so it would overflow the 17-bit int (which could not represent values above 65,535), and the behavior would not be defined by the C standard.

If int is wider than 17 bits, there is no overflow in any case, and any negative result converted back to uint16_t wraps.

Improve this answer

Comments

2

The "mathematical rationale" comes down to the fact that all arithmetic stored in a uint16_t is done modulo 2^16. You can split it into two separate subtractions or do a single subtraction using parentheses and an integer promotion; once it lands in a uint16_t, it is reduced modulo 65536 in exactly the same way.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.