The deceptive loop

Question

Look at the following program and try to ascertain the number of times the while loop will run. (The code below is in Java but the concept involved herein will apply to other programming language like C, C++ etc.)

class Deceptive{
    public static void main(String args[]){
        int c=34;
        while(c>5){
            c++;
        }
        System.out.println("Loop Over");
    }
}

Short concise answer
(What is happening?)

On first glance it may appear that the loop will run infinite times since the value of c is apparently increasing continuously — but on closer inspection or actual execution one will see that the loop will terminate after some time. The important point to understand over here is that an integer variable occupies four bytes in memory and if we keep on adding one to it it will assume the lowest possible integer (a negative value) value once it assumes the maximum possible value. Once the integer variable assumes the negative value the condition c>5 becomes false; the loop terminates and the message Loop Over is displayed.

Long detailed answer
(Why is it happening?)

Let us see why an integer variable become negative after successive addition of one. An integer variable occupies four bytes of memory. Any value which we store in an integer variable is stored internally in binary. The negative values are stored using Two’s Complement representation.

For example 34 would be stored in binary as
0000 0000 0000 0000 0000 0000 0010 0010
If a negative number is to be stored, say -34, then the Two’s Complement of the same needs to be taken (Two’s complement of a binary representation is obtained by swapping all ones and zeros and adding one to the result). After swapping zeros and ones of the binary digits of 34 we will get the following
1111 1111 1111 1111 1111 1111 1101 1101
On adding one to the above binary representation we will get the Two’s Complement of 34 which is essentially -34 i.e. 1111 1111 1111 1111 1111 1111 1101 1101 + 1 will be
1111 1111 1111 1111 1111 1111 1101 1110

So 34 is represented in binary as 0000 0000 0000 0000 0000 0000 0010 0010 and -34 is represented as 1111 1111 1111 1111 1111 1111 1101 1110. The important point to note over here is that the first digit of the binary representation of 34 is 0 and the first digit of the binary representation of -34 is 1. This property will hold for all integers which can be stored in four bytes i.e. the first bit in the binary representation of a negative number in Two’s Complement representation is 1 and the first bit in the binary representation of a positive number in Two’s Complement representation is 0.

Now if we keep on adding one to the binary representation of 34 as the magnitude will increase number of zeros in the beginning of the number will decrease and there will come a time when the leftmost bit or the first bit will become 1 and at that point of time the number will actually be a negative number!

Highest positive 32 bit integer 2147483647 in binary representation is
0111 1111 1111 1111 1111 1111 1111 1111
If we add one to the above it will become
1111 1111 1111 1111 1111 1111 1111 1111
which is a negative number in Two’s Complement representation because the first bit is 1.

One thought on “The deceptive loop

  1. Pingback: Magic number | www.VinaySingh.info

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.