Almost Always Unsigned

Written by Dale Weiler

Twitter

GitHub

Last updated Saturday, January 1, 2022 The need for signed integer arithmetic is often misplaced as most integers never represent negative values within a program. The indexing of arrays and iteration count of a loop reflects this concept as well. There should be a propensity to use unsigned integers more often than signed, yet despite this, most code incorrectly choses to use signed integers almost exclusively. Most of the motivation of this article applies to C and C++, but examples for other languages such as Go, Rust and Odin will also be presented in an attempt to establish that this concept applies to all languages, regardless of their choices (for instance C and C++ leave signed integer wrap undefined), but rather is intrinsic to the arithmetic itself.

The arguments against unsigned #

There are a lot of arguments against the use of unsigned integers. Let me explain why I think they’re mostly incorrect.

The safety argument #

The most typical argument against the use of unsigned integers is that it’s more error prone since it’s far easier for an expression to underflow than it is to overflow. This advice is so common that the official

Google C++ Style Guide outright discourages the use of unsigned types. We’ll see in the following arguments where these safety issues come from and how to easily avoid them with trivial idioms that are easier to understand than using signed everywhere. We’ll also see that these arguments are incorrect most of the time as they encourage continuing to write and use unsafe code.

The loop in reverse argument #

When the counter of a for loop needs to count in reverse and the body of the loop needs to execute when the counter is also zero, most programmers will find unsigned difficult to use because i >= 0 will always evaluate true. The temptation is to cast the unsigned value to a signed one, e.g: for (int64_t i = int64_t(size) - 1; i >= 0; i--) { // ... } Of course this is dangerous as it’s a narrowing conversion, with a cast which silences a legitimate warning. In C and C++ it invokes undefined behavior when given specific large values and most certainly is exploitable.

Most applications would just crash on inputs >= 0x7ffffffffffffffff. The typical argument is that such a value would be “pathological”. Not only is this argument incorrect, it’s even more dangerous which we will see later. This danger is one of the supporting arguments behind always using signed integer arithmetic. The argument is incorrect though, because int64_t would never permit a value >= 0x7ffffffffffffffff. It’s only avoiding the issue in that the specific problematic numeric range above that limit is no longer allowed. Tough luck if you needed a value that large and if you followed the sage advice of Google to always used signed and had that large value, well now you have a significantly worse problem, as you now invoked signed overflow unconditionally. Which for languages like C and C++, invoke undefined behavior. While languages like Go and Odin will wrap and have the wrong numeric ranges in the loop as a result of that wrap behavior. The correct approach here is that unsigned underflow is well-defined in C and C++ and we should be teaching the behavior of wrapping arithmetic as it’s useful in general, but it also makes reverse iteration as easy as forward. for (size_t i = size - 1; i < size; i--) { // ... } The approach here is to begin from size - 1 and count down on each iteration. When the counter reaches zero, the decrement causes the counter to underflow and wrap around to the max possible value of the unsigned type. This value is far larger than size, so the condition i < size evaluates false and the loop stops. Languages like Rust chose to make even unsigned underflow a trap representation in Debug builds, but specific features like Range will let you safely achieve the same efficient wrapping behavior on underflow with much cleaner syntax. for i in (0..size).rev() { // ... } With this approach, no casts are needed, no silent bugs are introduced, and the “pathological” input still works correctly. In fact, this form permits every possible value from [0, 0xffffffffffffffff), covering the entire range.

It should be noted that if size == 0 these loops still work because 0 - 1 produces the largest possible value of the unsigned type which is larger than size (still 0) and so the loop never enters.

The difference of two numbers can become negative #

When you want to compute the difference (or delta) between two numbers, it’s often the case to want to express that as: delta = x - y; Although most of the time the sign isn’t needed so you tend to write and see: delta = abs(x - y); The argument is that unsigned is dangerous here because if y > x then you get underflow. The problem with this argument is it’s not valid because the code itself is simply incorrect regardless of the signedness of x and y. There are values for both x and y which will lead to signed integer underflow. So like before, in languages like C and C++, you just unconditionally invoked undefined behavior since signed integer underflow is undefined. It turns out that computing differences safely is actually quite hard for signed integers because of underflow, even in languages which support wrapping behavior for them, e.g INT_MAX - INT_MIN is still going to be incorrect even. There just isn’t a trivial way to do this safely; this is the best technique I currently know of. if ((y > 0 && x < INT_MIN + y) || (y < 0 && x > INT_MAX + y)) { // error } else { delta = abs(x - y); } For unsigned integers however, it’s much easier to just write delta = max(x, y) - min(x, y); This will always give the absolute difference safely. It might be personal preference, but I find this easier to read too. The name delta is no longer necessary as the expression is self-documenting.

Computing indices with signed arithmetic is safer #

An extension to the above argument is that if you have a more complicated expression to compute an index it’s just safer to express that with signed. I think this argument primarily comes from an invalid intuition of underflow and overflow, yet it manifests for signed in significantly worse ways. Lets take the most trivial “slightly more complicated” expression to compute an index as an example: the middle of interval.

int mid = (low + high) / 2;

I picked this as a real-world, non-contrived example. You can expect to find this in binary searches, merge sort, and pretty much any other divide-and-conquer algorithm.

This is how most people would write it. The average of low and high, truncated to the nearest integer. When the sum of low and high exceeds 2^31-1 the sum overflows to a negative value and the negative stays negative when divided. Using a larger signed integer type here does not save you either because it’s easy for the sum to exceed 2^63-1 too. Like the previous example, this code is just not ideal. In fact, computing the mid-point of two variables safely is pretty much impossible in any language without the help of a library function because with wrapping or otherwise, there are specific inputs that fail. One common solution for signed is to rewrite it to this idiom, which still fails for high = INT_MAX and low = INT_MIN. int mid = low + (high - low) / 2; Sticking with unsigned integers, you might think you can write it the obvious way you originally intended to precisely because underflow is well-defined but we’ll see that this has problems too. size_t mid = (low + high) / 2; This doesn’t actually work for e.g: low = 0x80000000 and high = 0x80000002, which would underflow and produce 2 which divided by 2 produces 1, when the correct value is actually 0x80000001. Where unsigned does benefit here is when these are used as indices into an array. The signed behavior will almost certainly produce invalid indices which leads to memory unsafety issues. The unsigned way will never do that, it’ll stay bounded, even if the index it produces is actually wrong. This is a much less-severe logic bug, but can still be used maliciously depending on context. The correct safe way to do this regardless of signedness is to convert everything to unsigned and account for the wrapping with masked addition.

T midpoint(T x, T y) { // U is the unsigned version of your type T, or same as T if T already unsigned // digits is the number of numeric digits (not including sign) in your type T. // std::numeric_limits<T>::digits in C++ is helpful here. U shift = digits - 1; U difference = (U)x - (U)y; U sign = y < x; U half = (difference / 2) + (sign << shift) + (sign & difference); T mid = (T)(x + half); return mid; }

C++ actually has std::midpoint which does precisely this.

Unsigned multiplication can overflow #

When multiplying unsigned variables it’s a concern that such expressions will easily overflow and produce a value far smaller than the correct value. This is a very common complaint for memory safety specifically because unsigned multiplication is most often seen when allocating arrays. It’s tempting to write the following in C. malloc(sizeof(Object) * n) If such an expression were to overflow then malloc will allocate and return a pointer for memory not actually sufficiently large for all n Object. Again, signed here does not save us, in practice this will silently avoid the memory safety issue by over-allocating around 4 GiB of memory had you used int since a negative casted to size_t becomes about that large. Random resource exhaustion is not exactly a better situation to be in either. There are a couple better ways to write this. The first obvious one is just use calloc. That does have a zeroing cost though and doesn’t help if you need to realloc. Languages like C++ and Go noticed this problem and solved them in cleaner ways, eliminating the need for the dangerous multiply.

C++ new Object[n];

Go make([]Object, n);

// But it also even has an explicit n * m form as well. make([]Object, n, m);

Those don’t apply generally though. It’s very trivial to check if x * y would overflow though and you should just learn the extremely simple and obvious test.