Thread: Unsigned Overflow/underflow/truncation - C

  1. #1
    Registered User
    Join Date
    Nov 2019
    Posts
    135

    Unsigned Overflow/underflow/truncation - C

    Consider the following code segments, and select the correct answer regarding the value of c at the end:

    Code:
    int main()
    {
        int a = 1;    
        unsigned int c = ((a - 2) / 2);
        return 0;
    }
    
    int main()
    {
        int a = 1;
        unsigned int c = a - 2;
        c /= 2;
        return 0;
    }

    Select one:
    The value of c is different because of truncation.
    The value of c is different because of overflow or underflow.
    The value of c is the same in both cases.
    The value of c is the same because truncation removes the effect of overflow or underflow.


    The answer is the second one - I would like to understand why is it.

    At the first main - we have a variable of type int so when we divide it by 2 - and we get minus 0.5 - truncation happens - which leaves us with 0.

    At the second main - we assign to unsigned int a negative value - which creates some enormous number (the process of overflow or underflow - I'm not sure).

    But, I have read a little about unsigned int and overflow/underflow in respect to that - for example, here
    :
    c++ - Why is unsigned integer overflow defined behavior but signed integer overflow isn't? - Stack Overflow

    So what's going on here with this negative value assignment?

    Thank you.

  2. #2
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    First thing, both your main functions are the same.

    An integer on most systems I've used is 4 bytes so let's consider it to be 4 bytes for now. 4 bytes is 32 bits where each bit can be a 0 or 1 (thankfully, we don't have qubits just yet!).

    A signed integer has 31 bits available for the number you want to store and 1 bit for its sign (+ve or -ve) (0 means +ve and 1 means -ve : only for the first bit of course, the rest is your number)
    An unsigned integer has all 32 bits available for the number you want to store.

    I'm assuming you know how the numbers are stored in binary and how to do binary to decimal conversion and the reverse process too.

    A signed integer can store numbers in the range (-2^31) to (2^31 - 1).
    An unsigned integer can store numbers in the range (0) to (2^32 - 1).

    Let's take A = 1

    When A is a signed integer (int is signed by default), it's binary representation is:
    A = 1 = 00000000 00000000 00000000 00000001 (The first 0 to represent that it is positive)

    Now, A = -1 can be found out using the two's complement method. I'm hoping you know this too. If not, you can google it up and read about it. It's basically inverting all the bits (0 to 1 and 1 to 0) and adding 1 to the result. Most compilers these days use the two's complement method.
    A = -1 = 11111111 11111111 11111111 11111111 (notice the first bit is 1, which means -ve)

    Now, imagine what would happen if A was unsigned holding that mess above. The first bit that denotes the sign of the number in a signed int is no longer needed for representing the sign because the range of unsigned int (remember that the compiler is going to be treating A as an unsigned int as we told it to do so) is (0) to (2^32 - 1). Guess what? That, the representation just above this line of A = -1, is (2^31 - 1)....
    Hence, your really large number.

    Also, you cannot overflow unsigned integers.

    [EDIT]
    Paid a visit to the link you attached to the Stack Overflow discussion and thought of linking it here too in case you haven't read it.

    Nowadays, all processors use two's complement representation, but signed arithmetic overflow remains undefined and compiler makers want it to remain undefined because they use this undefinedness to help with optimization. See for instance this blog post by Ian Lance Taylor or this complaint by Agner Fog, and the answers to his bug report.
    Also, code written in a good way will never have or will at least try to avoid any signed overflows. It's sometimes very painful to deal with in some competitive programming questions in edge case scenarios in the test cases.
    [/EDIT]
    Last edited by Zeus_; 12-03-2019 at 10:12 AM.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  3. #3
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    Zeus -
    Amazing answer - thank you!
    I understood all this explanation, I think so at least.

    But, one thing that I didn't understand here - what's the meaning of the answer to this question:
    The value of c is different because of overflow or underflow.

    We have reached an agreement there is no overflow/underflow here at all...
    And you said - Both of the main functions are the same - In what manner they are the same?

  4. #4
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Quote Originally Posted by HelpMeC View Post
    We have reached an agreement there is no overflow/underflow here at all
    It is a case of underflow. With unsigned values underflow and overflow are well-defined. With signed values they aren't. Underflow is like turning an odometer backwards from 0, except in binary. So the mains are different.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  5. #5
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    John - I'm not sure I got it. How do we identify in this particular case that we have at the second main actually an underflow?

    And equivalently - how would we identify if an overflow occurs?

    Thank you.
    Last edited by HelpMeC; 12-03-2019 at 11:38 AM.

  6. #6
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    > Both of the main functions are the same - In what manner they are the same?

    In the first main, you've written c = ((a - 2) / 2) in one line. In the second main, you've written c = a - 2 in one line and then c /= 2 in a different line. In the end, both are the same thing, whether you divide by 2 on the same line or you divide by 2 on a different line.

    > We have reached an agreement there is no overflow/underflow here at all...

    Nooo! You're trying to assign a signed value to an unsigned value... a = 1, a is a signed integer. c is an unsigned integer. You assign c = a - 1 and so you'd expect c to be -1 but as I explained, -1 in binary is 11111111 11111111 11111111 11111111. The compiler treats this representation as an unsigned number and doesn't use the first bit to determine if its a positive number or not (which it would have done in case c was a signed number but its not) because unsigned numbers cannot be negative (look at the range I mentioned). So, when you display c, it is simply the decimal value of 11111111 11111111 11111111 11111111 which is (2^32 - 1).
    Now, if c was signed, lets say, then the compiler would have used the first bit i.e. 1 to determine whether it is positive or negative. First bit being 1 means it is negative. Now, using the two's complement rule you can determine that the number is -1 and that's what you would get in the display.

    When I said unsigned int doesn't overflow, I meant that when you perform operations like bitshift, etc you get defined behaviour.

    Example: (Assume int to be 8 bits for simplicity in this example. So, your range for unsigned int would be (0) to (2^8 - 1) and for signed int (-2^7) to (2^7 - 1)

    Code:
    int a = 127; // signed by default. binary: 01111111. 0 in the first bit indicates +ve
    
    print a; // 127
    
    a = a << 1; // left shift bits 1 time. binary: 11111110. Guess what? Signed bit is now 1, which means the number being held is -ve, to be exact: -2
    
    print a; // -2
    
    unsigned int a = 127; // binary: 01111111
    
    print a; // 127
    
    a = a << 1; // left shift bits 1 time. binary: 11111110. this isn't overflow, the behaviour is completely defined. Even if you left shift further, there is something called the "wrap around"
    
    print a; // 254
    c++ - Overflowing of Unsigned Int - Stack Overflow Take a look when you can.

    > The value of c is different because of overflow or underflow.

    When you assign a signed int, lets say, a value more than its maximum range (for a 32 bit i.e. 4 byte int, it is (2^31 - 1)), it overflows. I'll leave it to you to think what underflow would mean (imagine right shifting the sign determiner first bit to the right when it is set to 1. You'd have a 0 there meaning it is now positive all of a sudden from being a negative number)
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Zeus_
    In the first main, you've written c = ((a - 2) / 2) in one line. In the second main, you've written c = a - 2 in one line and then c /= 2 in a different line. In the end, both are the same thing, whether you divide by 2 on the same line or you divide by 2 on a different line.
    This is why I think this kind of exercise is helpful first to reason, then to test by compiling and running the program with output to help to see if one's reasoning is correct. Of course, just because the output is expected doesn't necessarily mean the reasoning is correct, but if the output is not expected, then it is highly likely the reasoning is wrong.

    So, adding this line just before the return 0 to both programs:
    Code:
    printf("%u\n", c);
    I compiled and ran the programs, and lo! The output of the first program was 0, and the output of the second program was 2147483647. So, you are wrong: "both are the same thing" is surely not true since they produce different results.

    The reason is that in the first program, you have signed integer division; in the second program, you have unsigned integer division. So if we follow the steps in the first program:
    ((a - 2) / 2) => ((1 - 2) / 2) => (-1 / 2) => 0

    To understand why we get 0 rather than something else, refer to the C standard:
    Quote Originally Posted by C11 Clause 6.5.5 Paragraph 6
    When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. [105] If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a; otherwise, the behavior of both a/b and a%b is undefined.
    You'll notice a note marker that I have rendered as [105]. The corresponding note reads: "This is often called ‘‘truncation toward zero’’."

    Notice that demonstrates a difference between dividing by 2 and right shifting by 1 where the left hand side is a signed integer with a negative value: if we wrote ((a - 2) >> 1) instead, then a final value of 0 is not guaranteed: the resulting value is implementation defined.

    For the second program:
    (a - 2) => (1 - 2) => -1 => (unsigned int)-1 => 4294967295 => 4294967295 / 2 => 2147483647

    Therefore, we can eliminate options c and d from the answer options. Is the difference due to truncation? No, the difference is due to the conversion to unsigned int before versus after the division by 2. This conversion from -1 to unsigned int could be seen as integer overflow, although one that is well defined in the standard and thus not regarded as overflow from that perspective, hence b is the best answer.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Nov 2019
    Posts
    135
    Zeus and laserlight - thank you, it was very helpful.

  9. #9
    Registered User
    Join Date
    Aug 2019
    Location
    inside a singularity
    Posts
    308
    Thanks for clearing that! It's technically the same but not same, I see. @HelpMeC, sorry for the wrong info.

    @laserlight, can you link me to the C Standard you use? I think I have the wrong one downloaded, as there is no 6.5.5 division in this. I have the right copy of C++ standard, I think, but please link me to the one you have so I can be sure.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook, The Wizardry Compiled

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Zeus_
    @laserlight, can you link me to the C Standard you use? I think I have the wrong one downloaded, as there is no 6.5.5 division in this. I have the right copy of C++ standard, I think, but please link me to the one you have so I can be sure.
    I buy PDF copies of the standards, so I can't link you to them. Uh, it's possible I opened the wrong one: it should have been C11, but because I was in a rush, it's possible it's actually say, C++. This core behaviour is the same the other way though.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Did I check for overflow or underflow properly?
    By deathslice in forum C Programming
    Replies: 7
    Last Post: 03-17-2016, 02:21 PM
  2. throw underflow?
    By stefanyco in forum C++ Programming
    Replies: 23
    Last Post: 10-08-2011, 11:37 AM
  3. Stack underflow
    By homer_3 in forum C Programming
    Replies: 5
    Last Post: 09-02-2009, 01:28 PM
  4. handling overflow, underflow etc
    By broli86 in forum C Programming
    Replies: 8
    Last Post: 07-03-2008, 07:10 AM
  5. memory underflow.
    By newbie_grg in forum C++ Programming
    Replies: 4
    Last Post: 01-26-2003, 11:19 AM

Tags for this Thread