Introduction

Bits

An established atomic unit for conveying and representing information is a binary digit or, briefly, a bit.

A bit can assume two possible states, namely either 0 or 1.

Of course we can have alternative meanings associated to state 0 and state 1. For example, 0 may mean false and 1 may mean true, or 0 may mean white and 1 may mean black:

_images/i0e.png _images/i1e.png

Historical remark. Claude E. Shannon [A mathematical theory of communication. Bell System Tech. J. 27 (1948) 379–423, 623–656] attributes the suggestion of using the word “bit” in this context to J. W. Tukey.

Data

In computing, data consists of bits.

In fact, it makes sense to define the word “data” in a computing context to mean “a sequence of bits”. This is the definition that we adopt.

This definition is convenient because it allows us to easily and unequivocally measure the amount of data that we have, that is, the number of bits the sequence. This also makes it easy to determine whether we can store the data in a storage device with a known storage capacity in bits.

Another reason why we want to define “data” to mean “a sequence of bits” is that it forces us to adopt an appropriately low-level perspective to computing, given our goal to understand the computer as a machine.

A sequence of bits is something that is simple and tangible enough for a machine to operate on.

Data and its format

By our definition, data is nothing but a mundane sequence of bits.

What makes data interesting is that we can agree on conventions and standards on what the data means or represents. Such agreed conventions and standards that attach a meaning to the data are called the format of the data.

Example 1. Here is a particular sequence of 29058 bits:

111111111111111111111110001111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000111001111111111111111111111111111101111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111000110011110111100111011111111111111011111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111100100111011111000110011111100111110111111011011111011101111100011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111101011100111101100110111111011111101111100110111110011001110000111000011111111111001111111111111111111111111111111111111111111111111111111111111111111111111111001111111010110011111011101100111101111111011111001001111110110001101101110110011100111110011111111111111111111111111111111111111111111111111111111111111111111111111110111111110100011111110111011101110011111110111110010011111101101010110011101110111000111101111111111111111111111111111111111111111111111111111111111111111111111111111101111111100000111111101110011001101111111101111101100111111011010001100111111101110110111101111111111111111111111111111111111111111111111111111111111111111111111111111011111111000000011111000000111000111111111011111011001111111110110111001101111011101101111011111111111111111111111111111111111111111111111111111111111111111111111111110111111110001110011100001101110001111111110000000110011111011101111110011011110111011101110111111111111111111111111111111111111111111111111111111111111111111111111111100111111001011110011011111011110111111111101111101101111110111011111100110111101111011011101111111111111111111111111111111111111111111111111111111111111111111111111111001111110110111110110111110011101111111111011111011011111101100111111011100000001110110011011111111111111111111111111111111111111111111111111111111111111111111111111111001111001101111100101111110111011111111110111110110011110011001111110111001111011101110110111111111111111111111111111111111111111111111111111111111111111111111111111111001100111011111100011111101110111011111101111101110111101110011111101110111110111011100100111111111111111111111111111111111111111111111111111111111111111111111111111111000011110111111110111111011101110111111011111011100100111100111111001001111101110111101001111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111001111111111111111100011111111111111010011111001101111000111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111011011111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111111111011111111111111111111111110111111111111111111111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111101110111111111111111111111000000011111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111011101111110110011111111100111110111111111111111111110011101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111110110011111101110111111011011111110111111111111111111100011011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111101100111111001101111110111111111001111111111111111111100000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111011011111110011011111101111111110111111111111111111111001001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111100110111111110110111111011111111011111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000001101111111011101111110111111000111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110001110011011111110111000000001111100111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111110110111111101110000000011111001111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111101110111111011101111110111110011111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111011101111110111011111101111110111111111111111111111001110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111110111011111011110111111011111111111111111111111111110001101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001111100110011000111101111110111111111111111111111111111101101011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111000111111011111101111111111111111111111111111011100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111000111111111111111111110111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111110011111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111111111111111111111110110000110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111111111111111111111111111111111000001100000000001100000000001111111111111111111001111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111010111111110011111101100011011111111000000111111101111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111110100111111110111110111110110000001110111111111111101111101100111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111011101111111101111101111110101111101101111111111111001111010000011101111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011100111011111111011111011111110011111011011111111111111001101001110011011111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111110100000110000111110111101111111100111100111011111111111111010010111110010111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111110101111111101100011111111001110111110001111111111111001101111110101111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111101011111111000010111111110100011111100000111111111110011011111101011111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111010111111110111101111111111000111111011111111111111101110111111010111111101111111111111111111100000000111111111111111111111111111111111111111111111111111111111101111101101111111101111101111110110110011110111111111111111101101111110101111110111111111111111111100111111110001111111111111111111111111111111111111111111111111111111011111011011111111011111011111101101110111101111111111111111010111111011011111101111111111111111110011111111111100111111111111111111111111111111111111111111111111111110111101110000000110111111011110111011110111011111111111111110100111110110111111011111111111111111011111111111111110111111111111111111111111111111111111111111111111111100000111111000111101111111011001110111101110000000111111111101101111011110111110111111111111111100111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111000111111111011100011111111111110011001101111100111011111111111111111011111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100111111110001111111111111111100111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111011111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111011111111111111111111111111111111111111111111110111111111111111111111111101111011111111111111111111111111111111111111111111111110111111111111101111111111111111111111110111111111111111111111111111111111111111111111001111111111111111111111111111100111111111111111111111111111111111111111111111111110111111111111011111111111111111111111101111111111111111111111011111111111111111111111011110111110000000000111111110110110011111111111001111000011111111111111111111111100111111111110111111111111111111111111011111111111111111111100001111111111111111111110111101110111100111111111111011101000000110011100011001111011011101111110111110011101111111111001111111111111111111111110111111111111111111111011011111111111111111111001111011101111011111111111100111110111101100111010010111110010111011111100000001111111111111110011111111111111111111111101111111111111111111110110111111111111111111110111110111011110111111111111011111011111101000101110101111110101110111111001111111111111111111101111111111111111111111111011111111111111111111101101111111111111111111101111101110111101111111111101111110111111010100011101011111001011101111110011111111111111111111001111111111111111111111111111111111111111111111011011111111111111111111000000011101111011111111111011111111111110101101111010111110110111011111110111111111111111111110011111111111111111111111011111111111111111111110110111111111111111111110000000111011110111111111110111110111111101011111101101111011101110111111100000111111111111111100111111111111111111111110111111111111111111111101100011111111111111111101111101110111101111111111011111101111111010111111011010000111011101111111000111111111111111111101111111111111111111111101111111111111111111111011110111111111111111111011111011011111011111111110011111011111110101111110110110111110111011111110111111111111111111111011111111111111111111110111111111111111111111100101101111111111111111110011110110111110111111111110111110111111011011111101101111111101110111111101111111101111111111110111111111111111111111101111111111111111111111011010111111111111111111101111101100111101111111111101111110111110110111111011011111111011101111111011111111001111111111100111111111111111111111011111111111111111111110110101111111111111111111011111011001111011111111111011111100110011101111110110111111110111000000100111111110011111111111101111111111111111111101111111111111111111111101101011111111111111111111111111111111110111111111111011001110011111111111111101111111101110011100100000001100111111111111011111111111111111111011111111111111111111110111010111111111101111111111111111111111101111111111110000111111111111111111111111111111111111111111000011111011111111111111011111111111111111101111111111111111111111101110011111111110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111110011111111111111110011111111111111111111111011010111111111100111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111110011111111111111001111111111111111111111110110101111111110001110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111111111100111111111111111111111111011101011111111010011001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110001111111110011111111111111111111111110111011111111110100100111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101001111110011111111111111111111111111101110011111110011011011111110011111101110000001111111111111111111111111111111111111111111111111111111111111111111111111111111110011100000011111111111111111111111111111011010111111101110001111111100111111011101111110000011111000000011111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111110110101111111111110111111111011111110110011111100100000000001110110011111110111111111111111111111111111111111111111111000011111001111111111111111111111111111111111111001101011111111111111111111110111111101100111111111101111101111111110111111101111111110111110111111111111111111111111110111011110011111111111111111111111111111111111110111010111111111111111111111101111111011001111111111011111011111111100111111011111111101111101100000000111111111111111001110011100011111111111111111111111111111111111101110101111111111111111111111011111110111000000111110111110111111111001111110111111110011111001001111101111111111111110111110111000011111111111111111111111111111111111011011011111111111111111111110111111101111111101111101111101111111111001111101111111100111111010111111101111111111111101111110110100111111111111111111111111111111111110110101111111111111111111111001111111011111111011111011111011011111101011110111111111001111110101111111011111111111111011111101101000111111111111111111111111111111111101101011111111111111111111110111111110111111110011110111110000111111011011101111111110011111101011111100111111111111110111111001011010111111111111111111111111111111111011010111111111111111111111101111111101111111100111101111101111111100110111011111111110111111010111111011111111111101101111111010110110111111111111111111111111111111110110101111111111111111111111001100111011011111011111011110111111111001110110111111111101111110100000000111111111111011011111110001110101111111111111111111111111111111101001011111111111111111111110000011110111011101111110111100111111110111101101111111111011111011000000111111111111110110111111100011101101111111111111111111111111111111010110111111111111111111111111111111111111000111111101111000000000000111101011111111110111110110111111111111111111100001111111000111001101111111111111111111111111111110101101111111111111111111111111111111111111111111111011111000001111011111000111111111100111011101111111111111111110001011111110001111011001111111111111111111111111111101010011111111111111111111111111111111111111111111111111110111111111111111011111111111100110111011111110011111111100110111111110011110111001111111111111111111111111110110000111111111111111111111111111111111111111111111111111111111111111111111111111111111100011110111111001111111111001101111111100111100111001111111111111111111111111101100001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111110101011111111001111101111001111111111111111111111111010001011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101010111111110011111011111001111000000000001111111110100011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111010100111111100111111011111000000111111111000011111011010110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100101101111111001111110111111001111111111111111111110000101101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000011111110011111100111111111111111111111111111100001011011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110010111111000111111100011111111111111111111111111111110111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101100111110101111111110001111111111111111111111111011000010011111111111111111100000000000000111111111111111111111111111111111111111111111111111111111111111111111111111011101111101011111111111000111111111111111111111000000010010000000011010000001111111111111000111111111111111111111111111111111111111111111111111111111111111111111111110111011110010011111111111100011111111111110000000000000000010000000000000111111110001000000001111111111111111111111111111111111111111111111111111111111111111111111111111110011101100111111111111110001111111111100111111011111111101111111100000000000111001111110101111111111111111111111111111111111111111111111111111111111111111111111111111110111011001111111111111111000111111111001111111111111111111111111111111111111111111111001011111111111111111111111111111111111111111111111111111111111111111111111111011110101110011111111111111111100011111110000000000000000000000000000000000000000000000000010011111111111111111111111111111111111111111111111111111111111111111111111110111110011100111111111111111111111001111111111001111111111111111111111111111111111111111100110111111111111111111111111111111111111111111111111111111111111111111111111101111111111001111111111111111111111100001111110011111111111111111111111111111111111111111011101111111111111111111111111111111111111111111111111111111111111111111111111011111111111011111111111111111110111110000111110111111111111111111111111111111111111111110111001111111111111111111111111111111111111111111111111111111111111111111111110111111111110111111111111110000000111111110011001111111111111111111111111111111111111111101110011111111111111111111111111111111111111111111111111111111111111111111111101111111111100111111100000000111100111111000000011111111111111111111111111111111111111111011100111111111111111111111111111111111111111111111111111111111111111111111111011111111111100000000011111111111101111110111101111111111111111111111111111111111111111110111011111111111111111111111111111111111111111111111111111111111111111111111111011111111111000000000000000000000000000101100011111111111111111111111111111111111111111101110111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111001100000110111111111111111111111111111111111111111111011101111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111000000000011111011011111101111111111111111111111111111111111111111110111011111111111111111111111111111111111111111111111111111111111111111111111111011111111110000000000011111111001110010011111011111111111111111111111111111111111111111101101111111111111111111111111111111111111111111111111111111111111111111111111110111111100000111111111111111111001110110111110111111111111111111111111111111111111111111011011111111111111111111111111111111111111111111111111111111111111111111111111101111110011111111111111111111111001100011111101111111111111111111111111111111111111111110110111111111111111111111111111111111111111111111111111111111111111111111111111011110011111111111111111111111111011100111111011111111111111111111111111111111111111111101101111111111111111111111111111111111111111111111111111111111111111111111111110011101111111111111111111111111110011101111110111111111111111111111111111111111111111111011011111111111111111111111111111111111111111111111111111111111111111111111111110111011111111111111111111111111110111001111101111111111111111111111111111111111111111110110111111111111111111111111111111111111111111111111111111111111111111111111111101110111111111111111111111111111001110011111011111111111111111111111111111111111111111101101111111111111111111111111111111111111111111111111111111111111111111111111111011110111111111111111111111111110111100111110111111111111111111111111111111111111111111011011111111111111111111111111111111111111111111111111111111111111111111111111110111110011111111111111111111110011111000111101111111111111111111111111111111111111111110110111111111111111111111111111111111111111111111111111111111111111111111111111101111110000001111111111111110001111101101111011111111111111111111111111111111111111111011101111111111111111111111111111111111111111111111111111111111111111111111111111101111111111100000000000000001111111011011110111111111111111111111111111111111111111110111011111111111111111111111111111111111111111111111111111111111111111111111111111011111111111111101101111111111111100110011101111111111111111111111111111111111111111101110011111111111111111111111111111111111111111111111111111111111111111111111111110000000000011110011011111111111111011110111011111111111111111111111111111111111111111101100111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000011111111111100111101110111111111111111111111111111111111111111111011101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000111111111111011111101101111111111111111111111111111111111111111110111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111011111111111110111111011011111111111111111111111111111111111111111101110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111001110111111111111001111110010111111111111111111111111111111111111111111011101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111101111111111110111111110101111111111111111111111111111111111111111111011011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111011111111111001111111101011111111111111111111111111111111111111111110110011111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011110111111111110111111111010111111111111111111111111111111111111111111101110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111101111111111101111111111100111111111111111111111111111111111111111111011101111111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111001111111110011111111111001111111111111111111111111111111111111111110111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111011111111101111111111110111111111111111111111111111111111111111111101110111111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111110111111110011111111111101111111111111111111111111111111111111111111001101111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111101111111101111111111111011111111111111111111111111111111111111111110011001111111111111111111111111111111111111111111111111111111111111111111111111111111111110011111111001111111111111111111110111111111111111111111111111111111111111111100111011111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111011111111111111111111101111111111111111111111111111111111111111111101110011111111111111111111111111111111111111111111111111111111111111111111111111111111110010010111110011111111111111111111011111111111111111111111111111111111111111111011110111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000011111111111111111110111111111111111111111111111111111111111111110111100111111111111111111111111111111111111111111111111111111111111111111111111111111100111111111111110011111111111111111101111111111111111111111111111111111111111111100000000011111111111111111111111111111111111111111111111111111111111111111111111111110011000000000001110011111111111111111011111111111111111111111111111111111111111111001110000000011111111111111111100000000101111111111111111111111111111111111111111111000000011111111100000011111111111111110111111111111111111111111111111111111111111110000000111111000000000000110001111111111100000000111111111111111111111111111111111100101111111111111111100011111111111111101111111100011111111111111111111111111111111001110111111111111111111111111111111111111111111111111111111111111111111111111111111011101111111111111110000111111111111111000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111010011111111111111101101111111111111110001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110001111111111111111011011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Suppose now 0 means black and 1 means white. Suppose furthermore that we split the data into 145 segments of 190 consecutive bits (\(167 \times 174 = 29058\)), and stack the segments on top of each other to form an array with 167 rows and 174 columns. What we obtain is the following black-and-white rendering from an Xkcd strip:

_images/okay-human-xkcd-371.png

Observe in particular that to reconstruct the visual rendering as a \(167\times 174\) array, we needed to agree on a format for the data. That is, that the 29058 bits represent a black-and-white image of dimensions \(167 \times 174\), with a 0 indicating black and a 1 indicating white.

Example 2. Here is another particular sequence of 64 bits:

0100000000001001001000011111101101010100010001000010110100011000

In this case we are in fact looking at a sequence that, if interpreted as a double-precision floating-point number conforming to the IEEE 754 standard (in more precise terms, the format binary64 in IEEE Std 754-2008 IEEE Standard for Floating-Point Arithmetic), is an approximation of \(\pi\):

\[3.141592653589793\]

Incidentally, this sequence of 64 bits is exactly the internal representation of scala.math.Pi. Observe again that the data in itself is just a sequence of 64 bits unless we agree on a format for the data, that is, that the data has some agreed meaning beyond its bits.

Example 3. Here is a third sequence of 88 bits:

0100111101101011011000010111100100101100001000000110100001110101011011010110000101101110

Suppose we receive this sequence from outer space. In such a situation, one possible assumption is that this sequence is intended to initiate a dialogue and is created by someone or something who is capable of conversing using human conventions and terms.

So why not assume that the sequence encodes a string of Unicode characters using the UTF-8 character encoding? (Currently, UTF-8 is the dominant byte encoding for HTML pages on the World-Wide Web.) If we follow this intuition, we discover that the 256 bits encode the following string of 11 characters:

Okay, human

It appears that someone, or something, is in a conversational mood, and have no problem using Earth digital standards. Of course, again the data is just a sequence of bits, so in principle we could just as well be looking at a black-and-white image, or, say, a sequence of four double-precision floating-point numbers conforming to IEEE 754-2008.

Types of data

The examples above exposed us to two basic types of data:

  • Numerical data: data that encodes numbers.

  • Textual data: data that encodes a sequence of characters over a fixed set of characters.

Data may of course represent many other types of information. Data may be sound, video, executable binaries, printing instructions to a 3D printer, or essentially whatever we like, as long as we can agree on a format.

The two basic types however occur frequently enough that they should be known to all serious programmers. And in fact we already have had exposure to such data in programming terms, even if we may have not paid attention to the fact that we are in fact working with sequences of bits.

Let us now recall a bit of Scala. In particular, we observe that the division into two basic types is rather prominent in the basic types used in Scala. Indeed, most Scala programs involve:

  • Numerical data: integers (Byte, Short, Int, and Long) or floating point numbers (Float and Double), or

  • Textual data: individual characters (Char) or strings (String).

Fixed-length data, words, word length

At hardware level, computers process data in units that consist of a fixed number bits. Such units are called words.

The length of a word is the number of bits in it. The maximum length of a word that is supported by the processor for general-purpose computations is called the word length of the architecture.

For example, you may have heard that your computer has, say, a 64-bit central processing unit (CPU). In practice this means that the processor is physically built to compute with 64-bit words of data when it executes one operation. In most cases the hardware also offers direct support to compute with smaller words than the full word length. In particular, a 64-bit architecture typically supports operations on 32-bit, 16-bit, and 8-bit words.

Although Scala is a hardware-independent language, Scala has been designed to take advantage of the available hardware features as they are available. Accordingly, the basic value types in Scala have fixed lengths that parallel the word operations typically supported in hardware.

More precisely, the integer value types in Scala have the following fixed lengths in bits:

  • Byte (8 bits),

  • Short (16 bits),

  • Int (32 bits), and

  • Long (64 bits).

(Some architectures may not support 64-bit operations in hardware, in which case such operations will be simulated in software using the available hardware. For example, a 32-bit processor may simulate a 64-bit operation using several 32-bit operations.)

The number of states for a sequence of b bits. A fundamentally important fact to understand about a \(b\)-bit word is that each of its \(b\) bits can independently be in exactly one of two possible distinct states, either 0 or 1. Thus, the word can be in exactly one of \(2^b = 2\cdot 2\cdot\ldots\cdot 2\) distinct states.

In particular this implies the following number of distinct states for the typical word lengths:

\[\begin{split}2^8 &= 256,\\ 2^{16} &= 65536,\\ 2^{32} &= 4294967296,\\ 2^{64} &= 18446744073709551616.\end{split}\]

Variable-length data

Data may also have a variable length. In this case the data is processed one word at a time at hardware level.

For example, think about a string such as

"Okay, human".

A string is a sequence of characters whose length may be arbitrary, that is, the length is not restricted by the format of the data. (We will review common string formats in more detail below.)

Variable-length data is in practice restricted only by our ability to store the data, which depends on the available storage capacity, ranging from cache memory inside the processor, to main memory, to secondary storage devices (such as an individual hard drive), to networked storage solutions for massive data. Of course, not all data needs to be stored. That is, data may be processed without storing it.

Indeed, in great many applications the data has an unknown length. Think about the sequence of key presses that a user effects at a keyboard. A key is pressed, then released, then the next key is pressed, and so forth. We simply do not know how many key presses and releases will occur, and in what order. Similarly so if we are running a networked device that accepts incoming data from the network that must be processed somehow.

In such settings one rather focuses on the rate at which the data arrives, and the latency at which the program (or device) must process the data.

For example, a program must react to user key presses rather quickly (with low latency), or the user experience deteriorates. Similarly, when routing network traffic, the traffic must be forwarded to its intended destinations at the same rate as it arrives, or the traffic will in general overwhelm the device.

Units of measure for data

One bit (1 bit, or 1 b) is the standard unit of measure for data and information. A common derived unit is one byte (1 byte, or 1 B) which is in practice understood to mean exactly 8 bits. A measurement in bits or bytes is often combined with an appropriate prefix indicating the order of magnitude. Here it is customary to either use the decimal base (base 10) or the binary base (base 2) to indicate magnitudes. If base 10 is used, the prefixes for order of magnitude follow the familiar SI definitions:

Prefix

Short

Order

kilo

k

\(10^{3}=1000\)

mega

M

\(10^{6}=1000000\)

giga

G

\(10^{9}=1000000000\)

tera

T

\(10^{12}=1000000000000\)

peta

P

\(10^{15}=1000000000000000\)

exa

E

\(10^{18}=1000000000000000000\)

zetta

Z

\(10^{21}=1000000000000000000000\)

yotta

Y

\(10^{24}=1000000000000000000000000\)

Example 1. One gigabit means one billion bits.

Example 2. If we use one square millimeter to store one bit of data, one megabit uses up one square meter, one terabit uses up one square kilometer, and one zettabit uses up more than the entire surface area of planet Earth. (Fortunately, in practice one bit can be stored in a considerably smaller area than one square millimeter!)

Example 3. It takes 8000 seconds (a little over 2 hours) to transfer one terabyte of data over a one-gigabit-per-second network link. Transfering one exabyte over the same link takes about 250 years.

Alternatively, orders of magnitude are measured in the binary base 2 using the IEC 80000-13 definitions:

Prefix

Short

Order

kibi

Ki

\(2^{10}=1024\)

mebi

Mi

\(2^{20}=1048576\)

gibi

Gi

\(2^{30}=1073741824\)

tebi

Ti

\(2^{40}=1099511627776\)

pebi

Pi

\(2^{50}=1125899906842624\)

exbi

Ei

\(2^{60}=1152921504606846976\)

zebi

Zi

\(2^{70}=1180591620717411303424\)

yobi

Yi

\(2^{80}=1208925819614629174706176\)

Here the prefix “kibi” stands for “kilobinary”, “mebi” stands for “megabinary” and so forth.

Warning

It is an unfortunate and common misuse to report the amount of data using the SI prefixes (that is, what appears to be in base 10) even if base 2 is actually intended. In particular, never assume that something that is reported using SI prefixes actually uses base 10 if this would lead to system failure when base 2 was actually intended. For example, you must not assume that \(1\) GB means exactly \(10^9\) bytes (the SI definition of \(1\) GB) if loss of data (or insufficient data transfer rate) will occur if you reserve storage space (or transfer bandwidth) only for \(10^9\) bytes (per second) when actually \(2^{30}\) bytes (per second) was intended.

Note

Observe that \(2^{10m}\) and \(10^{3m}\) diverge from each other at an exponential rate as \(m\) increases. For \(m=1\) the divergence is over \(2\%\) whereas for \(m=8\) it is already over \(20\%\)!

Witnessing the bits, in Scala

Now let us get in contact with the bits. This will in particular serve as motivation to study the bit-level formats for data.

To kick off our study of bits and data, we want to see the bits, at the console.

That is, we challenge you to take any value in any of the following types:

  • Byte

  • Short

  • Int

  • Long

  • Char

  • String

  • Float

  • Double

Then, use the functions tellAbout* defined below to tell about the value. (Let us not pay attention yet to how the functions actually work. For the time being we are happy just to see the bits.)

Each function

  • prints the sequence of bits that constitute the value, and

  • tells what the bits mean, in the meaning (format) that Scala attaches to the type.

Example 1. Assuming we have copy-pasted the tellAbout* functions into the console, let us take our favorite Int, say, let us take 123, and see what we get when we ask the function tellAboutInt to tell us about the value:

scala> val q = 123
q: Int = 123

scala> tellAboutInt(q)
I am a 32-bit word that Scala views as having format 'Int' ...
... my bits are, in binary, (00000000000000000000000001111011)_2
... or equivalently, in hexadecimal, 0x0000007B
... Scala prints me out as 123
... I represent the signed decimal integer 123
... I represent the unsigned decimal integer 123

All right. So an Int is in fact just a 32-bit word of data.

Example 2. Let us try the same with a negative integer. Here we see, among other things, how negative numbers are represented in binary using something called two’s complement representation. (The details of this representation need not concern us at this point.)

scala> val qq = -123
qq: Int = -123

scala> tellAboutInt(qq)
I am a 32-bit word that Scala views as having format 'Int' ...
... my bits are, in binary, (11111111111111111111111110000101)_2
... or equivalently, in hexadecimal, 0xFFFFFF85
... Scala prints me out as -123
... I represent the signed decimal integer -123
... I represent the unsigned decimal integer 4294967173

Example 3. A character is nothing but a sequence of bits that has been agreed to encode or represent that character.

scala> val c = 'n'
c: Char = n

scala> tellAboutChar(c)
I am a 16-bit word that Scala views as having format 'Char' ...
... my bits are, in binary, (0000000001101110)_2
... or equivalently, in hexadecimal, 0x006E
... Scala prints me out as n
... indeed, my bits acquire meaning via the Unicode standard
    https://www.unicode.org/
... I represent a single 16-bit Unicode character '\u006E'
... as a signed decimal integer, I am 110
... as an unsigned decimal integer, I am 110

Example 4. A string is nothing but a sequence of characters. That is, a sequence of bits that splits into encodings of characters, each of which is a sequence of bits.

scala> val s = "nakkisoossi"
s: String = nakkisoossi

scala> tellAboutString(s)
I am compound data that Scala views as having format 'String' ...
... in essence, I am a sequence of 11 consecutive 16-bit words,
    each of which Scala views as having format 'Char'
... the bits of this sequence are, in binary, (00000000011011100000000001100001000000000110101100000000011010110000000001101001000000000111001100000000011011110000000001101111000000000111001100000000011100110000000001101001)_2
... or equivalently, in hexadecimal, 0x006E0061006B006B00690073006F006F007300730069
... Scala prints me out as nakkisoossi

Example 5. Scientific and engineering computations require us to work with numerical data in floating point representation. This data has a more intricate format, but at heart every such number is just a sequence of bits.

scala> val d = scala.math.Pi
d: Double = 3.141592653589793

scala> tellAboutDouble(d)
I am a 64-bit word that Scala views as having format 'Double' ...
... my bits are, in binary, (0100000000001001001000011111101101010100010001000010110100011000)_2
... or equivalently, in hexadecimal, 0x400921FB54442D18
... Scala prints me out as 3.141592653589793
... indeed, my bits acquire meaning as specified
    in the binary interchange format 'binary64' in the
    IEEE Std 754-2008 IEEE Standard for Floating-Point Arithmetic
    https://dx.doi.org/10.1109%2FIEEESTD.2008.4610935
... this format is a bit-packed format with three components:
                            (0100000000001001001000011111101101010100010001000010110100011000)_2
    a) the sign
       (bit 63):             0
    b) the biased exponent
       (bits 62 to 52):       10000000000
    c) the trailing significand
       (bits 51 to 0):                   1001001000011111101101010100010001000010110100011000
... my biased exponent 1024 indicates that I am a _normalized_ number
    with a leading 1-digit in my significand and
    an unbiased exponent 1 = 1024 - 1023
... that is, in _binary radix point notation_, I am exactly
                                      (1.1001001000011111101101010100010001000010110100011000)_2 * 2^{1}
... or what is the same in _decimal radix point notation_, I am exactly
    3.141592653589793115997963468544185161590576171875

After these examples, you may want to try it out yourself or continue reading further. You can find the source code for the tellAbout-functions in the next Section.

Take any value in any of the aforementioned types.

Ask the console to tell about the value.

What you should observe is that, at heart, and as far as computing is concerned, everything is a sequence of bits.

Data and its format – a roadmap for this round

Our intent in this round is to make a guided tour of the most basic bit-level formats that every serious programmer should know. Not necessarily know by heart, of course, but the serious programmer should understand the implications that the bit-level and hardware-level representations have, to all programming.

Our tour will feature the two main types of data:

  • Numerical data — integers and floating-point numbers, and

  • Textual data — characters and strings.

These formats are common to all of digital computing and all programming languages, not just Scala.