Interesting Infinite loop using characters in C

Interesting Infinite loop using characters in C


Look at the following program:
int main(){
    int i;
    for(i = 0; i < 128; i++){
        printf("I am %d\n", i);
    }
    return 0;
}
In the above loop, the printf() statement will be executed 128 times. Now, look at the following program:
int main()
{
    char i;
    for(i = 0; i < 128; i++){
        printf("I am %d\n", i);
    }
    return 0;
}






Now can you guess how many times the printf() statement in the above “for” loop will be executed? Do you think this loop will also run 128 times? The answer is “NO”. It will run indefinitely. Let us investigate this program to know the truth behind it. Let us run this program and see its output. But each line is getting printed very fast that you can not even see it clearly. Let us slow down its speed of execution by adding some dummy loops. Look at the below program:

int main(){
    char i;
    for(i = 0; i < 128; i++){
        printf("I am %d\n", i);
  
                for(int j=0; j < 1000; j++)
            for(int k=0; k < 1000; k++)
    }
    return 0;
}
Additional loops have been added after the print statement. These additional loops will run 1000×1000 times and consume some time. This will slow down the overall speed of the program and now you will be able to see each output line clearly as shown below:
I am 0
I am 1
...
...
...
I am 126
I am 127
I am -128
I am -127
I am -126
...
...
...
...
Did you noticed anything in the above output? It seems from the program that 128 will come after 127 and the loop will get terminated. But -128 has come after 127 and -128 is less than 128 which satisfies the condition and hence the loop does not stop. But the question is why -128 comes after 127. Let us explore the reason.
Explanation: Usually, a character variable takes 1 byte (8 bits) of memory to store a character. Among these 8 bits, the most significant leftmost bit is sign bit and the remaining 7 bits represent magnitude. If the sign bit is 0 then it represents +ve value and otherwise -ve value. Therefore
Value of "i"    Binary representation
0                   0000 0000 
1                   0000 0001
2                   0000 0010
...
...
...
126                 0111 1110
127                 0111 1111
Now add 1 to it.
0111 1111
      + 1
---------
1000 0000
Hence now, our character variable “i” will hold “1000 0000”. Now, the sign bit is 1 which means this is a -ve number. Probably you know that negative integers are represented using 2’s complement format and 2’s complement representation of -128 is “1000 0000”. Therefore the value of “i” become -128 instead of +128. Therefore 0, 1, 2, …, 127, -128, -127, …, -1, 0, 1, 2… will continue.
But the similar thing does not happen in the first program where “i” was an integer variable. Because the size of an integer variable is 2 bytes or 4 bytes depending on your OS. If the size of integer variable is 2 bytes (16 bits) then can you tell the minimum value of “n” which will make the following loop an infinite loop?
int main(){
    int i;
    for(i = 0; i < n; i++){
        printf("I am %d\n", i);
    }
    return 0;
}
Maximum +ve integer that can be represented using 16 bits is “0111 1111 1111 1111” or 65535. When “i” becomes equal to this maximum value then the next increment makes it -65536 instead of +65536. Therefore the minimum value of “n” will be 65536.

Post a Comment

2 Comments

  1. It is undefined whether or not a char is signed or unsigned. So on some computers, this program would not cause an inifinite loop.

    ReplyDelete