01 - Data (1/2)

At the core, a computer is a glorified calculator. It manipulates numbers. This means that whether we browse videos online, listen for music, or play a multiplayer game, all we see is built off numbers.

Building a robust understanding of this simple idea will be useful as we explore and "rebuild" C++ from its most elementary pieces.

→ Principle

Excellence in (pretty much) any domain is better demonstrated by a deep mastery of its basics, rather than a catalogue of its most obscure subtleties.

Binary

If you can read in English, chances are you are familiar with numbers expressed in base ten (decimal). In this numeration system, there are 10 different digits (0..9), and, for instance, a 3-digit number can express 1000 different values: from 0 to 999.

The computer internally uses a different numeration system, where there are only two different digits (0, 1). We can call it "base two", or binary.

In the same way that in base ten, 10 really means "one more than our highest digit 9"; in base two, 10 means "one more than our highest digit 1", and thus represent the number two.

In binary, a 3-digit number can only express 8 different values: 0, 1, 10 (two), 11 (three), 100 (four), 101 (five), 110 (six), and 111 (seven). It makes the numbers very long, but apart from this it doesn't change much.

A digit in binary is called a bit.

There are 10 types of people: those who understand binary and those who don't.

Note

We won't go in details over the binary representation of numbers for now as it is not required for our current purpose. If you wish to investigate the subject, there are many good resources online.

Octet

An Octet is nothing more than a binary number made of 8 binary digits (8 bits). It can express 256 different values: from 0 to 11111111 in binary, which in decimal is 255.

If you are bothered by the binary, it is fine to just admit an octet is a number that can have one of the 256 values between 0 and 255 (included).

Example

In this chapter we will use the number 163 for our examples.

Since it is within the [0..255] range, it can be represented as an Octet. In binary it is written as: 10100011.

Byte

A Byte is the smallest "addressable" unit of memory for a computation system. We will unpack what this means later on. In practice, it is almost always the same thing as an Octet: an 8-digit binary number.

▸ Almost? ...

If we want to be very accurate, in C++, the only guarantee we have is that a Byte is at least 8 bits long. It could be more.

The Texas Instrument TMS320C28x architecture is a good example: in this architecture, a Byte is made of 16 digits.

Nowadays, such cases are exceptions, rare and far-apart. We will assume 8-bits Bytes in this course, as it is the common case and adapting what will be said to exotic larger-Byte cases should be straightforward.

If we write portable code (code that should work on any computer) we can only rely on the "at least" guarantee and consider that on most architectures, a Byte cannot express more than 256 distinct values.

The important difference for us is that an octet is an 8-digit binary number, while a Byte is "what the computer works with". We are specifically interested in the latter.

So a Byte is the smallest kind of number the computer can work with. It is made of at least 8 binary digits, and thus can express 256 distinct values.

Bytes as characters

Since the early 80s, we have been using a standard called ASCII to match numbers between 0 and 255 to specific characters.

To be precise, the ASCII standard existed since 1961, but only maps numbers between 0 and 127 to characters. The remaining mapping for numbers between 128 and 255 (included) is known as "extended ASCII", and comes in different flavours such as Windows-1252, ISO 8859-1, or CP437, so that in practice Linux and Windows machines can sometimes disagree on less common characters.

Example

Since the number 163 is beyond 127, it is part of the extended ASCII values, where standards can disagree.

With Windows-1252 and ISO-8859-1 extensions, 163 maps to the character '£'.

On older systems (typically IBM) using the CP437 extension of ASCII, 163 represents the character 'ú'.

It is worth noting that the character '1' in the ASCII standard is encoded by the number 49. Although this number can seem arbitrary when expressed in decimal, it makes more sense for those familiar with its binary representation (32 + 16 + 1): numbers are encoded with a 48 prefix + the encoded number.

ASCII is a very common way of interpreting numbers as (Latin) characters, but by no means the only one.

Bytes as true/false, on/off, yes/no values

Such value pairs are called Boolean values (from George Boole), and are extremely common as they represent the simplest switch between two states, such as the dark/light theme switch in the upper-right corner of this page, the ever-present tickbox, or a "yes/no" answer.

Although only one binary digit (0, 1) would be sufficient to encode this information, in C++ at least a full Byte (8 bits) is used for the boolean representation. The reasons for this will make more sense later in this series, but for now we can say this is because a Byte is the smallest unit of memory the system can work with.

Through the boolean lens, numbers are interpreted in this way: if the number is 0, it is false; otherwise, it is true.

Example

So our 163 is true if we look at it as a boolean value.

Phineas meme: "Isn't it a little wasteful? - Yes, yes it is"

Now, programmers usually hate wasting. If you are curious you can expand this box:

▸ Can we do better? Bytes as multiple booleans...

Sometimes, we want to store several true/false values, for instance when storing user preferences which are often a collection of yes/no answers. In this case, we sometimes decide to look at the Byte as multiple true/false values at once.

Since a simple true/false value can be expressed using a single binary digit (0, 1), and a Byte is made of 8 binary digits, we can store the values of 8 true/false values in a single Byte.

The downside of this approach is its added complexity: it is a little more involved and more error-prone to write and retrieve these values.

Readers who are familiar with binary representations probably understand this immediately.

Since a Byte is a number made of 8 digits (bits) that can take one of two values each (0 or 1), each digit can encode a true (1) or false (0) value.

You could visualise the Byte as a row of 8 switches:

8 switches

Each switch is one of the 8 digits, and when the switch is off, that specific digit is 0; when that switch is on, that specific digit is 1.

Example

The number 163 in this representation would be Switch 1, 3, 7, and 8 in position "On", and Switches 2, 4, 5, and 6 in position "Off".
Or the sequece true, false, true, false, false, false, true, true.

Note how this matches the binary representation of 163 .

Signed Bytes

A range from 0 to 255 is useful, but sometimes we also want to use negative values. Since our Byte can only represent 256 distinct values, we will have to repurpose some of these values to become negative.

[0..127] [128..255]


We achieve this by splitting the values of the Byte in two. The first half remains unchanged: [0..127] continue to represent the numbers from 0 to 127, but the second half, from 128 to 255 is moved to the negative range.

[0..127] [128..255]
We have to be a little careful there. In a similar way that the character `'1'` was an interpretation of the number `49`, the negative numbers [-128..-1] are an interpretation of the numbers in the range [128..255].

[-128..-1] [0..127] This value is still 128, but it now represents -128 This value is still 255, but it now represents -1
To look at it the other way around: [0..127] [-128..-1] 0 127 128 255

After 127, we start interpreting values as negative number, from -128 to -1 in ascending order.


Example

In this representation, our 163 is above 127, so it is interpreted as a negative number: -93.

Subtlety

Notice the asymetry between the largest 127 and the lowest -128 values that can be represented with a signed Byte.

This is due to having 0 between the strictly positive and strictly negative numbers, but an even number of possible values for a Byte (256). So there are 128 strictly negative values, 1 zero, and 127 strictly positive values.

Because of this, taking the negative of a signed Byte whose value is -128 is an invalid operation (Undefined Behaviour), as it would yield 128 which cannot be represented as a signed Byte. In practice, although doing this operation could lead to a crash (Undefined Behaviour is something we should avoid as much as possible), many compilers would return -128 as the result for this operation (-(-128) => -128), which is obviously mathematically incorrect, and can be quite confusing.

▸ Why? (Requires familiarity with binary representations) ...

In practice, to negate a signed integer, the CPU is likely to invert all the bits and add 1.

Yes, that works. In all the valid cases, that is.

  • Consider 1. Inverting all the bits gives 11111110 in binary. And adding 1 to this gives 11111111, 255 in decimal, which, if you check above, happens to be the representation of -1,
  • Consider -127, which is 10000001 in binary. If we invert it, we get 01111110. Then add 1 => 01111111, 127 in decimal.
  • Consider 0. Inverting all the bits gives 11111111 in binary. Add 1 and every digit carries to the next, until the carry exceeds the number of digits, leaving only 0s: 00000000.

But what happens with -128? We apply same pattern, of course.

  • -128 is 10000000 in binary. When we invert it, we get 01111111. To which we add 1, giving 10000000, back to -128 in decimal.

Bytes as light intensity

Some interpretations are relatively straight-forward. The screen displays pixels, and these pixels can send more or less light intensity. We can interpret the value of a Byte as how bright we want a pixel to be.

Example
  • At  0 , it is black.
  • At 163, it is a medium light-ish gray.
  • At 255, it is white.

Bytes as ℜeal numbers

We now have positive and negative numbers, but there's a whole infinity of numbers between 0 and 1. How do we tap into this range? As we have said before, we only have 256 different values for a Byte, so we will have to find strategies to use these values wisely. The most common way is through floating-point, but floating-points are complicated.

Bytes as Fixed point

For now, we will look at the much simpler fixed point.

Counting from 0 to 255 was easy enough. What if we decided they were not wholes but halves? Now we have 0, 0.5, 1, 1.5, 2... all the way up to 127.5; What if we decided we are counting quarters, or eighths? This is just another filter of interpretation.

We could combine the Signed Byte trick with this, and have signed values that represent 8th: [-16, -15.75, -15.5, -15.25 .. -0.5, -0.25, 0, 0.25, 0.5 .. 15.25, 15.5, 15.75].

Example

For 163, as a signed fixed-point with 5 signed integer binary digits and 3 fractional binary digits (i.e. made of 8th), we have already worked out that it reads as -93 as a Signed Byte. If we consider it made of 8th, we have -93/8 = -11.625.

▸ Bytes as floating point...

The floating-point representation will make more sense later on, but I wanted to introduce it here, as it is heavily used in all kind of applications, and more tricky than most people realise. Don't worry if you don't get the details, it's a folded section for a reason. If you remember that floating points are a tricky representation, that's good enough.

One key idea behind this representation is that we usually care about precision for small numbers, and not so much for large ones. For instance, over a centimetre or an inch, I care about a millimetre. But over a kilometre or a mile, not so much.

So we will try to spread our 256 values in such a way that we have many values close together near 0, and fewer as we step away from 0.

This representation breaks our 8 binary digits into 3 parts:

  • The first digit is for the sign of the number: 0 for positive numbers, 1 for negative numbers.
  • Then a few digits for something called the Exponent.
  • And the remaining digits for what is called the Mantissa.

There are different format. For our purpose, we will choose:

  • 1 binary digit (bit) for the sign,
  • 4 bits for the Exponent,
  • 3 bits for the Mantissa.

The short version is that the number is computed as sign 2 Exponent Mantissa , but this is very imprecise. We will see below it is much more complicated than this.

3 bits for the mantissa means that every 8 (23) values, we will double the space between our values when we step away from 0.

Three exponent bands of an 8-bit float, each twice the width of the last A number line divided into three labelled regions I, II, and III, laid out edge to edge. Each region holds exactly 8 representable values, evenly spaced within it, but region II is twice as wide as region I, and region III is twice as wide as region II. The gap at each junction equals the new band's spacing, the moment the step size doubles. I II III 8 values 8 values 8 values width w width 2w width 4w

But that's not even half of the headache.

  • The sign is simple enough, let's celebrate this.
  • The Exponent has special values. Both it's minimum and maximum values as special.
  • The other values of the Exponent that are less special have a "bias". Nothing romantic, it means that we have to subtract a specific value (the bias) from the raw number to know its value. For our format, we will choose a bias of 7. So if the raw value of the Exponent is 1, we should read the exponent as -6. If the raw value is 7, we should read it as 0. If the raw value is 14 (1 less than the maximum value we can represent with 4 bits), we should read it as 7.
  • The Mantissa is a fixed point number. It is scaled based on its number of bits: if it has 3 digits, it is divided by 23 (i.e. it represents 8th).
  • If the Exponent raw value is not 0 (which is a special case mentioned above), the Mantissa should be read as if there was an additional digit set to 1 before it (implicit leading 1).

And then there are all the special cases.

Example

Let's see what it would give for our 163 example.

163 in binary is 10100011. If we split it according to our format, we would get:

  • The first bit for the sign: 1, so our number will be negative.
  • The next 4 bits for the Exponent: 0100 in binary, which is 4 in decimal, for the raw Exponent.
  • The 3 last bits for the Mantissa: 011 in binary, which is 3in decimal.

The raw exponent is neither 0 nor 15, so we read it by subtracting 7 from it. 4 - 7 = -3.

Since the Exponent is not 0, we should read the Mantissa as a fixed point number made of 8th and add a leading 1 before it. Three 8th is 0.375, and with a leading 1, we get 1.375.

We can finally form the final result: - 2-3 × 1.375 = - 0.125 × 1.375 = -0.171875.

So the value 163, through the floating-point lense, is interpreted as -0.171875.

Don't worry if you didn't follow everything there, it isn't important for now.

The subtlety and complexity of floating point numbers is astonishing, but fortunately, their usage is simple. This makes them a double-edged sword: easy to use and powerful... until we start to look at them from up close.

What that complexity buys us

While this representation is particularly complex, it has a great advantage:

Even our naive 1-4-3 format allows to represent values both positive and negative with magnitudes as large as 240 (though near that magnitude consecutive values are spaced 16 apart), or as small as 0.015625 (with a gap of only about 0.002 between consecutive values at that scale).

Floating points should be used in situations where we accept and welcome this property: It is precise around 0 but that precision degrades as the values grow in magnitude.

The many Faces of a Byte

ℹ Recap

That was 6 (or 8 if you went through the secret sections) different ways to look at a single Byte. We are barely scratching the surface, but hopefully, you start to see how a universe made of nothing else than numbers might not be boring after all.

The concept behind these interpretations of a same number is fundamental for programmers, and we will encounter it at every turn: it is the notion of semantics : the specific meaning that the data encodes.

Let's take a few minutes to experiment and play with the different representations of a Byte we have discussed above.

◈ Interactive