CODEWITHSUNDEEP
c++castingoverflow
himbeerHummus
himbeerHummus

Reputation: 45

Overflow of an unsigned char in C++

I found following code snippet here https://www.toptal.com/c-plus-plus/interview-questions with the question: How many times will this loop execute? Explain your answer

unsigned char half_limit = 150;

for (unsigned char i = 0; i < 2 * half_limit; ++i)
{
    // do something;
}

The answer is infinite.

The expression 2 * half_limit will get promoted to an int (based on C++ conversion rules) and will have a value of 300. However, since i is an unsigned char, it is rerepsented by an 8-bit value which, after reaching 255, will overflow (so it will go back to 0) and the loop will therefore go on forever.

I guessed 45 times (300-255), because I remember that if you increment an unsigned integer counter, the counter will start at 0 again when it overflows. Okay, so it casts from an integer to an unsigned char, why its not 255 then?

Thank you

Upvotes: 0

Views: 3325

Answers (4)

user9872569
user9872569

Reputation: 

#include <iostream>

int main(int argc,char* argv[]){

    unsigned char half_limit = 150;

    for (unsigned char i = 0; i < 2 * half_limit; ++i)
    {
        printf("%.2X\n", i);
    }
}

compiled this code with mingw g++. gave me an infinite loop, printing the hexadecimel value of i shows that it gets resets every time it overflows. And perhaps when it overflows it sets a flag .. Correct me if I'm wrong

Upvotes: 0

eerorika
eerorika

Reputation: 238401

why its not 255 then?

Because 255 is less than 300. In next iteration, i will be 0 which is also less than 300. No number representable by 8 bit integer can reach 300.

Technically, the correct answer is that the number of iterations depends on the size of unsigned char. On a system that uses a 16 bit byte, there would be no problem.

Another issue with the answer is that "infinite" loops are not allowed in the language unless certain actions are taken within the loop - such as generating some output. So actually, the example program has undefined behaviour (assuming 8 bit byte). Quote from the standard:

[intro.progress]

The implementation may assume that any thread will eventually do one of the following:

  • terminate,
  • make a call to a library I/O function,
  • perform an access through a volatile glvalue, or
  • perform a synchronization operation or an atomic operation.

[ Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. — end note ]

Upvotes: 4

DeducibleSteak
DeducibleSteak

Reputation: 1498

2 * half_limit

is the same as:

int(2) * int(half_limit)

half_limit gets promoted to an integer to do the multiplication, and the result of the expression is 300. Thus,

i < 2 * half_limit

becomes

i < int(300)

where i gets promoted to an int to do the actual comparison, but since i is an unsigned char, it can never be bigger than 255 (assuming our unsigned chars are 8 bits), so that comparison is effectively:

int(smaller than 256) < int(300)

which is, of course, always true.

Upvotes: 1

Aykhan Hagverdili
Aykhan Hagverdili

Reputation: 29985

Arithmetic on types smaller than int first promotes them to int. For that reason 2 * half_limit is 300. Assuming the largest value unsigned char can represent is 255, all the values i can possibly have satisfy i < 2 * half_limit, thus this is an infinite loop.

Upvotes: 4

Related Questions