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 Java 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 Java specification will tell us that,
For int, from -2147483648 to 2147483647, inclusive (Java Language Specification - Java SE 26 Edition, § 4.2.1)
This likely raises another question. Why this range in particular?
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.
One reason for this is that the Java language is meant to ultimately be run in a Java Virtual Machine (JVM) and the official JVM specification states that:
int, whose values are 32-bit signed two's-complement integers, and whose default value is zero
Reals
How about x = 17.25? Let's take another look at the spec,
"The floating-point types are float and double, which are conceptually associated with the 32-bit binary32 and 64-bit binary64 floating-point formats for IEEE 754 values and operations, as specified in the IEEE 754 Standard" (Java Language Specification - Java SE 26 Edition, § 4.2.3)
This means that a float follows 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 1.
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: public class ThumbsUp { 2: public static void main(String[] args) { 3: byte[] thumbs_up = {(byte)0xf0, (byte)0x9f, (byte)0x91, (byte)0x8d}; 4: String s = new String(thumbs_up, java.nio.charset.StandardCharsets.UTF_8); 5: System.out.println(s); 6: } 7: }
Compiling and running it we get:
josephraskind@stargazer:/tmp/data$ javac ThumbsUp.java josephraskind@stargazer:/tmp/data$ java ThumbsUp 👍
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 Java 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 usingSystem.out.println(variable_name).) - Convert the number -17 to its 32-bit two's complement binary representation by hand. Verify your answer by writing a Java program that stores -17 in an
intand prints it out usingSystem.out.println(x). Then print its binary representation usingInteger.toBinaryString(x). 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? Verify by writing a Java program that prints0.1fusingSystem.out.printf("%.20f%n", 0.1f). - 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 Java program that prints each character of your name alongside its decimal ASCII value usingSystem.out.printf("%c %d%n", c, (int)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 Java program to verify your encoding using the same technique as Listing 2.
- 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.