Computers are very good at counting. But usually only within narrow limits. Here is an insight into where these limits come from and what goes wrong when they are exceeded.
The original German 🇩🇪 version of this article is here: Zählen wie ein Computer.
Counting for beginners
Most of us have been counting for so many years that we can’t even remember when we counted for the first time. Initially, most of us probably used our fingers. At first we stopped at 10, but at some point we realized the trick with the tens transition. We later extended it to the hundreds and thousands transition.
So this video should come as a surprise to very few people. Nor that the odometer on the left and the speedometer-style “counting clock” on the right show the same counting processes.
However, it might be a little more unexpected if we count beyond 999 on our three-digit odometer. Because we are missing the fourth digit for the thousands, this is cut off and we end up back at 000; we are missing the option of adding thousands. (Perhaps some people still remember the days when cars had five-digit odometers and you had a “brand new” car again after having driven for 100,000 kilometers…)
The counter clock has the same problem. So you actually already know all the problems from the decimal system; there is nothing new.
Counting for computers
But now let’s switch to the binary system, to computers. In the decimal system, the value of the last digit is counted once, the second digit is multiplied by ten, the third digit has an importance of ten times ten, i.e. a hundred. And at each position we have a choice of ten digits, 0 to 9.
| Digit | Fourth last | Third last | Second last | Last position |
|---|---|---|---|---|
| Decimal system | 10*10*10 = 1000 = 10³ | 10*10 = 100 = 10² | 10 = 10¹ | 1 = 10⁰ |
| Binary system | 2*2*2 = 8 = 2³ | 2*2 = 4 = 2² | 2 = 2¹ | 1 = 2⁰ |
We count in a very similar way in the binary system: the value of the last digit is multiplied by one, the second digit by two, the third digit by two twice, i.e. four times. Two digits, 0 and 1 (or in other words: power off or on), are sufficient for each position.
| Binary system | Calculated | Decimal system |
|---|---|---|
| 000 | 0*4 + 0*2 + 0*1 | 0 |
| 001 | 0*4 + 0*2 + 1*1 | 1 |
| 010 | 0*4 + 1*2 + 0*1 | 2 |
| 011 | 0*4 + 1*2 + 1*1 | 3 |
| 100 | 1*4 + 0*2 + 0*1 | 4 |
| 101 | 1*4 + 0*2 + 1*1 | 5 |
| 110 | 1*4 + 1*2 + 0*1 | 6 |
| 111 | 1*4 + 1*2 + 1*1 | 7 |
As in the decimal system, the same applies here: To increment a position which is already at the maximum digit, this position wraps back to zero and a carry is applied to the next higher position. In the decimal system, this is the case when changing from 9→0, in the binary system as early as 1→0. The second digit is therefore already incremented every second step.
Here, too, we have a discontinuity when we “count up” from (binary) “111” to “000”. With a finite number of bits for the representation of a number, this can never be avoided; adding more digits only delays this overflow.
Negative numbers
In many everyday situations, the positive numbers (and the zero) are enough. If we didn’t need more, we could finish here.
Sometimes, however, it is quite practical to be able to calculate with negative numbers. For example, on the Celsius thermometer in winter. Or to be able to calculate consistently with “meters above sea level“, even near the Dead Sea. Or simply to be able to display differences, for example in the case of inflows and outflows, in a uniform way.
For binary numbers, as we have seen above, two’s complement has become the de-facto standard (at least for whole numbers): The ingenious thing about this representation is that we don’t have to change anything in our calculation processes: Counting, adding or subtracting take place in the computer in exactly the same way as if all numbers were positive. We simply think of all numbers whose most significant bit is 1 as negative. Computation itself is unchanged; we only need a little additional brain power for input and output.
(At least if we ignore multiplication, division, size comparisons, or the test as to whether an overflow has occurred during an arithmetic operation. And floating point numbers, i.e. numbers with decimal places).
Another advantage of the two’s complement: we still only have one discontinuity, with three-digit numbers between “011” (+3) and “100” (-4). However, when counting from -4 to +3, no special handling is needed.
We accept the small inconvenience that there are more numbers below zero than above zero because two’s complement offers us so many other advantages in a simple, clear representation.
(For the mathematically inclined readers: The positional value of the leftmost (=most significant) digit in our 3-bit example is +4 for unsigned numbers, as we first got to know them, so a one in this position increases the value of the total number by 4. For signed numbers, i.e. if we also want to represent negative numbers, the value is -4; a one in this position decreases the number’s value by 4. Simply ingenious, isn’t it?)
| Bits for the number | Possibilities | Number range without sign | Number range with sign | Significance of the most significant digit |
|---|---|---|---|---|
| 3 | 2³ = 8 | 0 … 7 | -4 … +3 | ±4 |
| 4 | 2⁴ = 16 | 0 … 15 | -8 … +7 | ±8 |
| 8 | 2⁸ = 256 | 0 … 255 | -128 … +127 | ±128 |
| 16 | 2¹⁶ = 65’536 | 0 … 65’535 | -32’768 … +32’768 | ±32’768 |
| 32 | 2³² = 4’294’967’296 | 0 … 4’294’967’295 | -2’147’483’648 … +2’147’483’647 | ±2’147’483’648 |
| 64 | 2⁶⁴ ≈ 16 trillion | 0 … 16 trillion (approx.) | -8 trillion … +8 trillion (approx.) | ±8 trillion (approx.) |
Impact
We’ve probably all filled out those forms where a separate box had been set aside for each letter or number. Some will certainly have had the problem that the number of boxes for some number or text were not enough (or at least imagined what would happen if that ever were the case).
Our computers are also modeled on these box forms, in the truest sense of the word. And they have also inherited the same limits: in many databases and web forms, text fields have a maximum length, as do – see above – numbers, usually with predefined upper and lower limits.
And once many computers (or many parts of a larger program) have agreed on such a form (in computer science then a data format, API or protocol), it is very difficult to extend these limits later.
With numbers, there is the additional surprise that when counting up very large numbers, the values can suddenly become very large negative numbers.
Unfortunately, these limits play a key role in many IT security problems, as well as other problems such as the one I will be talking about in a follow-up article.
But the main impact will be explained in a follow-up article.
