CS211: Data
Table of Contents
Introduction
The world is the totality of facts, not of things — Ludwig Wittgenstein
In order to perform computations we must have something to perform computations on. After all, what good is addition if there is nothing to add? In computing, we call these computational necessities "data". Conceptually, data is an information abstraction. This abstraction has analogues to phenomena in the real world—meaning data represents something. For example, I may have data in the form of numbers which represent the dimmensions of a shipping container, or I may have data in the form of words which represent the list of students who made the Dean's list, or I may have data in the form of a graph which represents related artists on a music platform, etc.
What interests us most in this class is not what data is philosophically, but rather how it is stored within a computer.
How is Data Stored in a Computer?
Fundamentally, data can be stored in any way a computer architect sees fit. The earliest computers stored numbers as decimals within their circuitry. For example, the ENIAC used what was called Binary Coded-Decimal (BCD) wherein 10 binary digits (bits) were used to represent a single value, 0000000001 for 0, 0000000010 for 1, …, and 1000000000 for 9. It wasn't until the EDVAC that it became standard for computers to store numeric information purely in binary (0 for 0, 1 for 1,…, and 1001 for 9). As late as 1968, of the 139 available general purpose digital computers, "46 were decimal, 72 binary, 4 octal, 15 binary/decimal, 2 biquinary"1.
The switch to pure binary came from a desire to cut down on the amount of space taken up by numerical data. In the famous Report on EDVAC, John Von Neumann writes,
- "If one contemplates using a decimal system with either the Iconoscope or delay line memory one is forced into a binary coding of the decimal system—each decimal digit being represented by at least a tetrad of binary digits. Thus an accuracy of ten decimal digits requires at least 40 binary digits. In a true binary representation of numbers, however, about 33 digits suffice to achieve a precision of 10^10."
We'll talk more about memory later in the semester, but right now it will suffice to say that there must be something to "hold" our bits when we run out of register space—that is what we call memory.
In this lecture we'll answer two questions: "How are numbers stored in a computer?" and "How is text stored in a computer?".
How are Numbers Stored in a Computer?
In order to answer this, we first have to define what we mean by "numbers". In an effort to avoid any sort of philosophical detour, we'll assume a "common sense" definition of "number": numbers are objects used to measure phenomena. A human being has two eyes, one nose, ten fingers, etc. We may also want to distinguish between simple, countable numbers and infintesimal, continuous numbers. In C, these kinds of numbers are distinguished by having different types (we will talk about this extensively in the future). int matches to integers, or countable numbers, and float matches to reals, or continuous numbers.
Integers
When I write the C code x = 17, what is actually being stored inside the computer? The answer is that there will exist a set of binary digits which will be arranged to represent the idea of the number seventeen within the machine. A trip to the C specification will tell us that,
- "A 'plain' int object has the natural size suggested by the architecture of the execution environment (large enough to contain any value in the range INT_MIN to INT_MAX as defined in the header <limits.h>)." (ISO/IEC 9899:2024 Draft, § 6.2.5)
This likely raises more questions than it answers. What is the "natural size" of an integer? How is anything about a computer natural? What is <limits.h>?
A lot of this has to do with the fact that C was made to be a language that could target hardware as best as possible by removing as much overhead as possible. Some systems may not benefit from an int being a fixed 4 bytes—for instance, smaller systems might want a 3 byte int. If I look in my /usr/include/limits.h file, I see the following:
1: /* Minimum and maximum values a `signed int' can hold. */ 2: # define INT_MIN (-INT_MAX - 1) 3: # define INT_MAX 2147483647
According to Listing 1, an int on my machine is between -2147483648 and 2147483647. Taking the log_2 of 2147483648 yields 31 (2^31 = 2,147,483,648) which means it takes 31 bits to encode that maximum number. From what you already know about computers it might seem odd to default to 31 bits for an integer. Why not 32? The reality is that an int does default to 32 bits due to the use of two's compliment. In two's compliment the most significant bit is a signed bit, meaning its presence/absence indicates a negative/positive value. For example,
- 0000 0000 0000 0001 = 1
- 1111 1111 1111 1111 = -1
It can be represented by the formula:
- (d^n-1 * -2^n-1) + (d^n-2 * 2^n-2) +…(d^1 * 2^1) + (d^0 * 2^0)
where n is the number of bits.
This means that 17 is stored as 0000 0000 0001 0001.
Reals
How about x = 17.25? Let's take another look at the spec,
- "There are three standard floating types, designated as float, double, and long double. The set of values of the type float is a subset of the set of values of the type double; the set of values of the type double is a subset of the set of values of the type long double." (ISO/IEC 9899:2024 Draft, § 6.2.5)
Somehow even more vague! Further on we find,
- "The float type matches the ISO/IEC 60559 binary32 format" (ISO/IEC 9899:2024 Draft, § F.2.1)
This means that a float follows the ISO/IEC 60559 standard which is equivalent to the IEEE 754 standard. It follows the following formula:
- (-1)^s + (1 + m) * 2^e
- Exponent bias = 127
- Exponent = e + bias
- m = fraction bits (start at 2^-1)
IEEE 754 Floating Point Specification sign exponent (8 bits) fraction (23 bits) | | | | | v v v v v +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | 0| 1| 0| 0| 0| 0| 0| 1| 1| 0| 0| 0| 1| 0| 1| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| 0| +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 31 30 23 22 (bit index) 0
First we see if the number is positive or negative, clearly it's positive so the signed bit is set to 0. Next, we need to represent 17.25 as a true binary number. We already know the non-fractional half is 10001. The fractional half is easy to get, all we need to do is follow the algorithm:
- Set f equal to the fractional half.
- Set f equal to f * 2.
- If f >= 1 record a 1; if not, record a 0.
- Repeat 1 until pattern emerges or we run out of bits.
.25 is rather simple, we multiply by 2 to get .5 (and tally a 0), then multiply by 2 to get 1 (and tally a 1). Since the remaining fractional half is 0, there's no further need to multiply. This gives us .01 in binary. Combine that with our 17 and that gives us 10001.01.
Next we convert 10001.01 to scientific notation, 1.000101 * 2^4. However many spaces we moved the decimal up is what we add to the bias. This gives us 127 - (-4) = 131 which is equivalent to 100000011 in binary. We then take the remaining bits after the decimal and store that in the fractional portion. Which gives us the IEEE 754 32-bit floating point number shown in Listing 2.
How is Text Stored in a Computer?
Text is where bit-based data representation and storage becomes much more abstract. There is an obvious direct mapping between representing the number 17 as decimal number and 10001 as binary number. It becomes much less obvious when trying to map 97 to 'a'.
One traditional way of representing characters is using ASCII encoding:
| Char | Decimal | Octal | Hex | Binary |
|---|---|---|---|---|
| A | 65 | 101 | 41 | 01000001 |
| B | 66 | 102 | 42 | 01000010 |
| C | 67 | 103 | 43 | 01000011 |
| … | … | … | … | … |
| Z | 90 | 132 | 5A | 01011010 |
ASCII encoding using a single byte (really 7 bits, 0 to 127) to encode all of the english alphabet, including uppercase and lowercase letters, common punctuation, symbols and digits, alongside specialty characters like the null character '\0' and the new line character '\n'. For example, the character string "101" would be encoded as the binary string 001100010011000000110001 ("0" is 0x30 and "1" is 0x31).
ASCII encoding works well for the English language, but begins to fall apart the moment more than 128 characters are needed. For example, languages like Japanese or Chinese need far more symbols than the basic 26 required for English works (52 if counting uppercase letters). The most popular solution nowadays is to adopt newer encoding standards like UTF-8 or UTF-16 encoding.
UTF-8
UTF-8 is a character encoding standard based on the unicode standard. It is by far the most popular text encoding and has the ability to encode 974,530 unique symbols2 (in reality, only a small fraction of that potential is realized). The encoding rules are simple:
| First Code Point | Last Code Point | Byte 1 | Byte 2 | Byte 3 | Byte 4 |
|---|---|---|---|---|---|
| U+0000 | U+007F | 0zzzzzzz | |||
| U+0080 | U+07FF | 110xxxyy | 10yyzzzz | ||
| U+0800 | U+FFFF | 1110wwww | 10xxxxyy | 10yyzzzz | |
| U+010000 | U+10FFFF | 11110uvv | 10vvwwww | 10xxxxyy | 10yyzzzz |
where the characters u to z, each representing a hexadecimal digit, are replaced by their constituent four bits uuuu to zzzz, from the positions U+uvwxyz.
Say I wanted to encode the thumbs up emoji (👍), I would first need to look up its UTF-8 value. Using the link here, we can see the code is U+1F44D. That places the emoji squarely in the last row of the above table. First I need to convert the code to binary U+1F44D → 0 0001 1111 0100 0100 1101 such that it matches with u vvvv wwww xxxx yyyy zzzz. Next we need to match the letters with their bits in the template: 11110000 10011111 10010001 10001101. In order to verify that this in C we should convert the binary into hexadecimal: 0xF0 0x9F 0x91 0x8D. The following C program can be used to double check our work:
1: #include <stdio.h> 2: int main() { 3: char thumbs_up[] = {0xf0, 0x9f, 0x91, 0x8d, 0x0}; 4: printf("%s\n", thumbs_up); 5: return 0; 6: }
Compiling and running it we get:
josephraskind@stargazer:/tmp/thumb$ gcc thumb.c -o thumb josephraskind@stargazer:/tmp/thumb$ ./thumb 👍
This only works if your terminal is UTF-8 encoded. This is almost always the case for Linux devices, but is not guaranteed for Windows systems (which tend to favor UTF-16 for historical reasons).
Hopefully, this gave you a bit more insight into what's going on behind the scenes when your using your computer!
Exercises
- Write a C program that stores 2147483647 in a variable of type
int, adds 1 to it, and prints it out. What do you see? Explain why. (You can print out numbers usingprintf("%d\n", variable_name).) - Convert the number -17 to its 32-bit two's complement binary representation by hand. Verify your answer by writing a C program that stores -17 in an
intand prints it out usingprintf("%d\n", x). Then print it again usingprintf("%u\n", x)(unsigned). What do you see and why? - Convert 0.1 to IEEE 754 32-bit floating point by hand following the algorithm given in the lecture. What do you notice about the fractional part? What does this imply about storing 0.1 in a
float? - The string
"101"is given in the lecture as the binary string001100010011000000110001. Using the ASCII table from the lecture, encode your first name as a binary string by hand. Then verify by writing a C program that prints each character of your name alongside its decimal ASCII value usingprintf("%c %d\n", c, c). - Using the UTF-8 encoding table, encode the character 'é' (U+00E9) by hand. Which row of the table does it fall in? Write a C program to verify your encoding using the same technique as Listing 3.
- The lecture mentions that ASCII uses 7 bits (0 to 127) despite being stored in a full byte. What happens to the 8th bit? Look up "extended ASCII" and write a short explanation of how different systems took advantage of that extra bit, and why this caused compatibility problems that UTF-8 was designed to solve.