Fun with overflowing integers
3 min. read

Today, I finally got around to fixing a fundamental issue with klog (my command line tool for time tracking): if someone were to use klog on a daily basis for a few trillion years, there would be an increased risk of incorrect computations due to integer overflow.

In particular, after precisely 9223372036854775807 minutes worth of time tracking, the total time amount would wrap around and continue at -9223372036854775808 minutes. I wouldn’t go as far to call this a time bomb ticking right there, but you know, time is money, and that’s where things get serious (especially in this ballpark).

In all fairness, while the practical value of this fix is rather academic, it was mainly a fun exercise to dive into the bits and bobs of overflowing integers. I created a small Go library called safemath for this purpose,1 which I published on its own.

Integer overflows

Signed integers are basic (primitive) types, whose values are represented by fixed-width bit patterns. The minimum and maximum values depend on the machine architecture and on the declared width. On 64-bit systems, for instance, the default numeric range stretches from -9223372036854775808 (lowest possible value) to 9223372036854775807 (largest possible value).

When using built-in mathematical operators such as + or *, the respective computations are carried out via simple bitwise instructions. That, however, does not include any logical checks whether the calculation would fit into the representable value range. If the result were to exceed the boundaries, it would do so silently, and in a way that wouldn’t make any sense from an arithmetic point of view.

One way to detect overflows2 is to run explicit checks on the operands ahead of time. For a computation with two operands A and B, an overflow would necessarily occur if:

One tricky thing is that the minimum and maximum numbers don’t have the same absolute value, which requires extra caution: for example, if one of the operands happens to be the minimum number, we cannot trivially compute the inverse value by multiplying by -1, and we also have to make sure that we don’t divide the minimum value by -1. It’s worse for multiplications, because while ½Min * 2 is okay, ½Min * -2 is not.

If overflow is defined behaviour3, we can also carry out the computation naively, and then run a check on the result. In this case, an overflow can be detected by inspecting the signs of the operands and the resulting value. The overflow conditions are:

  1. Another possible solution would have been a refactoring to using the math/big package. ↩︎

  2. If the overflow happens on the lower end of the range, it’s technically called “underflow”. ↩︎

  3. In C++ for example, signed integer overflow is undefined behaviour. ↩︎

My e-mail is:
Copy to Clipboard