Author: giovannidicanio

Last time, we discussed signed integer overflow in C++, and some associated subtle bugs, like summing a sequence of positive integer numbers, and getting a negative number as a result.

Now, let’s focus our attention on unsigned integer numbers.

As we did in the previous blog post, let’s start with an apparently simple and bug-free function, that takes a vector storing a sequence of numbers, and computes their sum. This time the numbers stored in the vector are unsigned integers of type uint16_t (i.e. 16-bit unsigned int):

#include <cstdint>  // for uint16_t
#include <vector>   // for std::vector

// Sum the 16-bit unsigned integers stored in the values vector
uint16_t Sum(const std::vector<uint16_t>& values)
{
    uint16_t sum = 0;

    for (auto num : values)
    {
        sum += num;
    }

    return sum;
}

Now, try calling the above function on the following test vector, and print out the result:

std::vector<uint16_t> v{ 10, 1000, 2000, 32000, 40000 };
std::cout << Sum(v) << '\n';

On my beloved Visual Studio 2019 C++ compiler targeting Windows 64-bit, I get the following result: 9474. Well, this time at least we got a positive number 😉 Seriously, what’s wrong with that result?

Well, if you see the sequence of the input values stored in the vector, you’ll note that the result sum is too small! For example, the vector contains the values 32000 and 40000, which are only by themselves greater than the resulting sum of 9474! I mean: this is (apparently…) nonsense. This is indeed a (subtle) bug!

Now, if you compute the sum of the above input numbers, the correct result is 75010. Unfortunately, this value is larger than the maximum (positive) integer number that can be represented with 16 bits, which is 65535.

Side Note: How can you get the maximum integer number that can be represented with the uint16_t type in C++? Simple: You can just invoke std::numeric_limits<uint16_t>::max():

cout << "Maximum value representable with uint16_t: \n";
cout << std::numeric_limits<uint16_t>::max() << '\n';

End of Side Note

So, here you basically have an integer “overflow” problem. In fact, the sum of the input uint16_t values is too big to be represented with an uint16_t.

Before moving forward, I’d like to point out that, while in C++ signed integer overflow is undefined behavior (so, basically the result you get depends on the particular C++ compiler/toolchain/architecture/even compiler switches, like GCC’s -fwrapv), unsigned integer “overflow” is well defined. Basically, what happens in the case of two unsigned integers being added together and exceeding the maximum value is the so called “wrap around“, according to the modulo operation.

To understand that with a concrete example, think of a clock. For example, if you think of the hour hand of a clock, when the hour hand points to 12, and you add 1 hour, the clock’s hour hand will point to 1; there is no “13”. Similarly, if the hour hand points to 12, and you add 3 hours, you don’t get 15, but 3. And so on. So, what happens for the clock is a wrap around after the maximum value of 12:

12 “+” 1 = 1

12 “+” 2 = 2

12 “+” 3 = 3

…

I enclosed the plus signs above in double quotes, because this is not a sum operation as we normally intend. It’s a “special” sum that wraps the result around the maximum hour value of 12.

You would get a similar “wrap around” behavior with a mechanical-style car odometer: When you reach the maximum value of 999’999 (kilometers or miles), the next kilometer or mile brings the counter back to zero.

Adding unsigned integer values follows the same logic, except that the maximum value is not 12 or 999’999, but 65535 for uint16_t. So, in this case you have:

65535 + 1 = 0

65535 + 2 = 1

65535 + 3 = 2

and so on.

You can try this simple C++ loop code to see the above concept in action:

constexpr uint16_t kU16Max = std::numeric_limits<uint16_t>::max(); // 65535
for (uint16_t i = 1; i <= 10; i++)
{
    uint16_t sum = kU16Max + i;
    std::cout << " " << kU16Max << " + " << i << " = " << sum << '\n';
}

I got the following output:

So, unsigned integer overflow in C++ results in wrap around according to modulo operation. Considering the initial example of summing vector elements: 10, 1000, 2000, 32000, 40000, the sum of the first four elements is 35010 and fits well in the uint16_t type. But when you add to that partial sum the last element 40000, you exceed the limit of 65535. At this point, wrap around happens, and you get the final result of 9474.

How of curiosity, you may ask: Where does that “magic number” of 9474 come from?

The modulo operation comes here to the rescue! Modulo basically means dividing two integer numbers and taking the remainder as the result of the operation.

So, if you take the correct sum value of 75010 and divide it by the number of integer values that can be represented with 16 bits, which is 2^16 = 65536, and you get the remainder of that integer division, the result is 9474, which is the result returned by the above Sum function!

Now, some people like to say that in C++ there is no overflow with unsigned integers, as before the overflow happens, the modulo operation is applied with the wrap around. I think this is more like a “word war”, but the concept should be clear at this point. In any case, when the sum of two unsigned integers doesn’t fit in the given unsigned integer type, the modulo operation is applied, with a consequent wrap around of the result. The key point is that, for unsigned integers, this is well defined behavior. Anyway, this is the reason why I enclosed the word “overflow” in double quotes in the blog title, and somewhere in the blog post text as well.

Coming back to the original sum problem, independently from the mechanics of the modulo operation and wrap around of unsigned integers, the key point is that the Sum function above returned a value that is not what a user would normally expect.

So, how can you prevent that from happening?

Well, just as we saw in the previous blog post on signed integer overflow, before doing the actual partial cumulative sum, we can check that the result does not overflow. And, if it does, we can throw an exception to signal the error.

Note that, while in the case of signed integers we have to check both the positive number and negative number cases, the latter check doesn’t apply here to unsigned integers (as there are no negative unsigned integers):

#include <cstdint>    // for uint16_t
#include <limits>     // for std::numeric_limits
#include <stdexcept>  // for std::overflow_error
#include <vector>     // for std::vector

// Sum the 16-bit unsigned integers stored in the values vector.
// Throws a std::overflow_error exception on integer overflow.
uint16_t Sum(const std::vector<uint16_t>& values)
{
    uint16_t sum = 0;

    for (auto num : values)
    {
        //
        // Check for integer overflow *before* doing the sum.
        // This will prevent bogus results due to "wrap around"
        // of unsigned integers.
        //
        if (num > 0 && sum > std::numeric_limits<uint16_t>::max() - num)
        {
            throw std::overflow_error("Overflow in Sum function.");
        }

        // The sum is safe
        sum += num;
    }

    return sum;
}

If you try to invoke the above function with the initial input vector, you will see that you get an exception thrown, instead of a wrong sum returned:

std::vector<uint16_t> v{ 10, 1000, 2000, 32000, 40000 };

try
{
    std::cout << Sum(v) << '\n';
}
catch (const std::overflow_error& ex)
{
    std::cout << "Overflow exception correctly caught!\n";
    std::cout << ex.what() << '\n';
}

Next time, I’d like to introduce a library that can help writing safer integer code in C++.