Counting like a computer


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.

“Simple” counting in the decimal system; three-digit numbers

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.

Incrementing 999 would result in 1,000; but we only have three digits…

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.

DigitFourth lastThird lastSecond lastLast position
Decimal system10*10*10 = 1000 = 10³10*10 = 100 = 10²10 = 10¹1 = 10⁰
Binary system2*2*2 = 8 = 2³2*2 = 4 = 2²2 = 2¹1 = 2⁰
Positional numeral systems: The value of different positions in different systems (looking at the right-most table cells first helps understanding the pattern)

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 systemCalculatedDecimal system
0000*4 + 0*2 + 0*10
0010*4 + 0*2 + 1*11
0100*4 + 1*2 + 0*12
0110*4 + 1*2 + 1*13
1001*4 + 0*2 + 0*14
1011*4 + 0*2 + 1*15
1101*4 + 1*2 + 0*16
1111*4 + 1*2 + 1*17
The first 8 numbers in the binary system

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.

Again, only three digits available, no four-digit “1000”. So, it wraps around from “111” (=7) to “000” (=0).

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 change nothing at the actual digits, we simply think of half of the (previously high) numbers now as negative numbers.

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 numberPossibilitiesNumber range without signNumber range with signSignificance of the most significant digit
32³ = 80 … 7-4 … +3±4
42⁴ = 160 … 15-8 … +7±8
82⁸ = 2560 … 255-128 … +127±128
162¹⁶ = 65’5360 … 65’535-32’768 … +32’768±32’768
322³² = 4’294’967’2960 … 4’294’967’295-2’147’483’648 … +2’147’483’647±2’147’483’648
642⁶⁴ ≈ 16 trillion0 … 16 trillion (approx.)-8 trillion … +8 trillion (approx.)±8 trillion (approx.)
The ranges of potential values in comparison: Both for our three-bit example and common sizes in computers. A 32 bit number can therefore represent any of about 4 billion different values.

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.

When a form like the above (this of course is just made up) has been widely accepted and is used everywhere and integrated in many different processes, it becomes hard to change it. This also applies to data formats and protocols in the computer/Internet fields. (The language of the form does not matter; it matters that any change will required thousands of organizations around the globe to coordinate that change.)

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.

, ,

Let’s stay in touch!

Receive a mail whenever I publish a new post.

About 1-2 Mails per month, no Spam.

Follow me on the Fediverse

Web apps


Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.