C++ integer overflow

Question

I'm just starting to teach myself C++, and have begun learning about integer overflow. Out of curiosity I wrote some tests just to see what occurs with certain integer values.

Here's my program:

#include <iostream>

int main()
{
    int x(0);
    std::cout << x << std::endl;

    x = x + 2147483647;
    std::cout << x << std::endl;

    x = x + 1;
    std::cout << x << std::endl;
    std::cout << std::endl;

    unsigned int y(0);
    std::cout << y << std::endl;

    y = y + 4294967295;
    std::cout << y << std::endl;

    y = y + 1;
    std::cout << y << std::endl;
}

And here's the output:

0
2147483647
-2147483648

0
4294967295
0

The output surprised me a bit, and I'm wondering if someone could explain why this happened, OR if the unexpected-ness of these results is expected; so this may just be the result of my specific machine.

Solution 1

Integers (generally) take a 32-bit representation. If you have 32 bits, you can address from 0 to 2³¹-1. i.e.,

00000000000000000000000000000000
00000000000000000000000000000001
.
.
.
01111111111111111111111111111111
^-------------------------------
signed bit

0 indicates a positive number, 1 indicates a negative number.

If you add 1 to 01111111111111111111111111111111, you get 10000000000000000000000000000000, which is -2147483648 in decimal.

Using an unsigned integer, there's no signed bit and, ipso facto, can have a number twice as large as your largest signed integer. However, when the number rolls over again (i.e., 11111111111111111111111111111111 + 00000000000000000000000000000001), you simply roll back to 00000000000000000000000000000000.

For a more in depth understanding, you can look at two's complement, which is how integers are represented in computers.

Solution 2

Signed integer overflow is undefined behaviour, while unsigned integer overflow is well-defined; the value wraps around. In other words, the value is modulo divided by 2^bits, where bits is the number of bits in the data type. Since you've a 32-bit int

4294967295 + 1 = 4294967296 % 2³² = 0

it results in 0 in the second case. The first case, from the language standpoint, is undefined.

However, most implementations employ 2's complement to implement signed integer types. A toy, signed 4-bit data type, implemented using 2's complement may be used to explain what happend in the first case. In this type

POS_MAX = 7 = 0111)₂

NEG_MAX = -8 = 1000)₂

The type can hold 2⁴ = 16 states, 8 positive (0 to 7) and 8 negative (-1 to -8).

POS_MAX + 1 = 0111)₂ + 1)₂ = 1000)₂

Since the first bit is set, it's a negative number, to find the actual value, do the inverse the two's complement (subtract 1 and flip bits)

1000)₂ - 1)₂ = 0111)₂

~0111)₂ = 1000)₂ = 8

Thus the final value is -8. All this is not defined by the language but this is what happened in your case, specifically.

Solution 3

Integer comes in two types. Signed and unsigned, both 32bits traditionally.

In first case you are using signed Integer. In this case, 1 bit is reserved for sign and rest of 31 are for magnitude. In this case, biggest number that can be saved is 2^31 - 1 = 2147483647. Adding one to it will affect most significant bit, changing number to negative. (Google 2's complement notation of numbers for more details).

In 2nd case, you are using unsigned int in which all 32bits are reserved for magnitude. Hence biggest number that be stored is 2^32 - 1. Adding one to it will make zero. E. G. Say we have 3 bit number system, 111 = 7. Adding one to it will make it 1000, but since its 3bit system, it will become 000 = 0

Comments

[mstbaum]

You're not flipping the counter. The max signed 8-bit number is 01111111 and when you add 1 it becomes 10000000, and depending on how your machine interprets negative numbers (just a signed bit, 1s compliment, 2s compliment) that number will be interpreted as some negative number. I see what you're saying when you say "flip" the counter, but I think that wording is confusing and misleading