Wrap around of integers in c

Question

I have been programming in c from quite some time. But never worked with programs where integer wrap around happens. I know that if integer is allocated 4 bytes then the range of integer becomes -2,147,483,648 to 2,147,483,647. And if we exceed the limit it just wraps around.

I was working with the following program to find out how wrap around happens.

#include <stdio.h>

int main() {
int n = 4, s = 2;

for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < n; ++j)
    {
        for (int k = 0; k < n; ++k)
        {
            s = 2 * s + 1;

        }
    }
}
printf("%d\n", s);
return 0;
}

I was using gdb to find out the values taken by the variable s. I found that when we are executing the innermost loop for 30th time the value of s becomes negative i.e -1073741825. Then for next iteration it becomes 2147483647 and for the 32nd iteration it becomes -1.

Then it remains as -1 forever. My doubt is why wrap around didn't happen after the value becomes -1. I know that the value of s in binary will be all 1's or FFFFFFFF in hex. And it wont change forever (internally it is updating but we can only see the last 32 bits so it's -1). But does the wrap around doesn't comes into picture this time? Is it compiler dependent? Or does gcc allow wrap around only once? Any kind of help would be appreciated. Thanks

Answer 1

Strictly speaking, overflow of signed integers is undefined behavior. In practice however, most implementation use 2's complement representation for integers and wraparound will work how you describe.

With that in mind, let's see what happens here.

As your loop progresses, eventually s will have a value of 1610612735. Up to this point nothing unusual happens. Now we multiply by 2 and add one. At this point the result overflows. Let's look at the hex representation of these numbers.

1610612735d = 0101 1111 1111 1111 1111 1111 1111 1111 b = 0x5FFFFFFF
0x5FFFFFFF * 2 = 0xBFFFFFFE
0xBFFFFFFE + 1 = 0xBFFFFFFF
0xBFFFFFFE = 1011 1111 1111 1111 1111 1111 1111 1111 b = -1073741825d

From a binary standpoint, multiplying by 2 is equivalent to a left shift of 1. This operation moves a value into the sign bit, giving you a negative value.

With the next operation, multiplying by 2 overflows again. This time the multiplication shifts a 0 into the sign bit where there was previously a 1, so the sign changes again:

0xBFFFFFFF * 2 = 0x7FFFFFFE
0x7FFFFFFE + 1 = 0x7FFFFFFF
0x7FFFFFFF = 0111 1111 1111 1111 1111 1111 1111 1111 b = 2147483647

The next iteration also overflows:

0x7FFFFFFF * 2 = 0xFFFFFFFE
0x7FFFFFFE + 1 = 0xFFFFFFFF
0xFFFFFFFF = 1111 1111 1111 1111 1111 1111 1111 1111 b = -1

Now we have -1. From here on out, there's no overflow:

-1 * 2 = -2
-2 + 1 = -1

Here's the same thing in hex:

0xFFFFFFFF * 2 = 0xFFFFFFFE
0xFFFFFFFE + 1 = 0xFFFFFFFF

As you can see doubling -1 and adding 1 gives you -1 again, so that's why it keeps repeating. This is also consistent with multiplication by 2 being a left shift of 1.