2012 April 11,

CS 111: Binary Numerals

Carleton College, Spring 2012

Prof. Joshua R. Davis, , Goodsell 106B, x4473

Introduction

Recently in class, we have discussed how all information inside a computer (numbers, text, images, video, etc.) is ultimately represented as numbers. In this tutorial, we learn how numbers themselves are represented inside computers in binary. Concretely, we practice conversion among binary, decimal, and hexidecimal numerals, and arithmetic with binary numerals. We learn a little about floating point numbers and RGB colors. We also glimpse a recurring theme in the design of computers and algorithms: the tradeoff between time efficiency and space (memory) efficiency.

In understanding binary notation, it is important to recognize the distinction between numbers and numerals. Numbers are mathematical objects subject to arithmetic operations (addition, subtraction, multiplication, and division), whereas numerals are the strings that we use to write numbers down. The distinction between numbers and numerals is important to any computer programmer, because numeric types (int, float in Python) have different capabilities than string types (str). For example, in Python 123 + 123 produces 246, while "123" + "123" produces "123123".

Throughout history, various cultures around the world have used various systems for representing numbers as numerals. For example, these three numerals all represent the same number:

• "1402" (in the western Arabic numeral system that we use in the USA)
• "one thousand four hundred two" (in plain English)
• "MCDII" (in Roman numerals)

When you carry out arithmetic calculations with numbers on paper, you probably use the standard algorithms that you learned in elementary school — "carry the 1" and all that. Those algorithms actually operate on the numerals that represent the numbers, rather than on the numbers themselves. Therefore your culture's choice of numeral system influences your culture's algorithms for arithmetic. It turns out that some numeral systems are more convenient — that is, produce more efficient algorithms — than others. For example, isn't adding numbers in Arabic numerals ("1402" + "713") easier than adding numbers in plain English ("one thousand four hundred two" + "seven hundred thirteen")?

Modern digital computers represent numbers as binary numerals. Binary means base-2, as opposed to the decimal or base-10 Arabic numeral system that we use in everyday life. Of course, when a computer performs an arithmetic calculation, it doesn't actually write the numerals as symbols on paper; it represents them using different voltage levels in electrical circuits. In order to understand what the computer is doing, we'll perform the same calculations, but on paper.

Converting Between Decimal and Binary

In this section we learn how to convert between decimal (base-10) and binary (base-2) numerals. Although technically I should enclose every numeral in quotation marks, because it is a string, I will omit the quotation marks so that we don't go crazy.

For starters, it is useful to know the first few powers of 2 and of 10.

When you write a number as a numeral in base 10, you are expressing it as a weighted sum of powers of 10. For example,

The digits of the numeral 1402 appear as the weights in these terms, in order: 1, 4, 0, 2. Each digit is between 0 and 10, including 0 but not including 10. That is, the possible digits in base 10 are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Similarly, when you write a number as a numeral in base 2, you express it as a weighted sum of powers of 2. The digits in the numeral are between 0 and 2, including 0 but not including 2. That is, the possible digits in base 2 are just 0 and 1. These are called the binary digits, or bits for short. For example,

To obtain the base-2 representation of 1402, we just read off the digits: 10101111010. In order to keep things straight between different bases, we attach subscripts to the numerals, indicating which base they're written in. For example,

1402₁₀ = 10101111010₂.

Some remarks: First, when we say that 1402₁₀ = 10101111010₂, we are not saying that the numerals 1402 and 10101111010 are equal (as strings); we're saying that the numbers that they represent are equal, in their respective bases. Second, when we write a numeral without a subscript, it will be understood to be in base 10, by default. Third, the subscripts are themselves numerals, which we interpret to be in base 10 (because they don't have subscripts themselves).

To convert from base-2 to base-10 we just reverse the process. For example,

Addition in Binary

Recall the standard algorithm for addition in base 10. You add the digits by column, going from right to left. As long as each column sum is less than 10, there is no problem. Whenever a column sum is 10 or greater, you carry a 1 into the next colum, and put the leftover in the current column. For example, here I'm adding 1402 and 713, and I have to carry a 1:

Addition in base 2 is similar. You add the bits by column from right to left. Whenever a column sum is 2 or greater, you carry a 1 and put the leftover in the current column. For example, here I add 01001110₂ and 00111101₂ and get an answer of 10001011₂:

You can add more than two numerals at a time in base 2, just as you do in base 10. When you add more than two numbers together, you sometimes have to carry multiple digits. In order to make this clear, let's do a big base-10 example first. In this example, I have to carry a 7 from the first column into the second column, I have to carry an 11 from the second column into the third and fourth columns, and I have to carry a 2 from the third column into the fourth column. Try it yourself, to make sure you understand how the carries work.

Here's an example in binary. I'm adding four numbers. I have to carry a 1₂ from the second column to the third, a 10₂ from the third column to the fourth and fifth, and a 1₂ from the fourth column to the fifth. Try it yourself.

Multiplication in Binary

Recall the standard algorithm for multiplying two numerals in base 10. You multiply the first numeral by each digit of the second numeral, lining up the products according to which digit of the second numeral produced them. Then you add the products by column. For example,

Multiplication in base 2 is similar. You multiply the first numeral by each bit of the second numeral, lining up the products according to the bit that produced them. In fact, base-2 multiplication is easier than base-10 multiplication in one aspect. Each bit is either 0 or 1, so multiplication by a bit means that you simply copy the number or not. Once you have all of the products lined up, you add them by column. For example,

Word Size

In base 10, small numbers have numerals with only a few digits, while large numbers have numerals with many digits. The same is true in base 2; the number 6 can be stored in three bits (6 = 110₂), while the number 338 requires nine bits (338 = 101010010₂). Suppose that I have a program with two variables, like this:

x = 6
y = 338

Remember that a variable is a named location in the computer's memory. That is, the 6 and 338 have to be stored in memory somewhere. Storing them requires 12 bits of memory, if we pack the two numerals together:

110101010010

However, packing numerals together like this causes problems. When we read 110101010010 out of memory, how do we know that it should be split up as 110 followed by 101010010, as opposed to 110101 followed by 010010 or 110101010 followed by 010? There is no way of knowing, unless we have somehow recorded information about how the numerals are packed in memory, in addition to the numerals themselves. And what if later in my program I change x to have value 12 = 1100₂ instead of 6 = 110₂?

x = 6
y = 338
...
x = 12

Now I need four bits to store the value for x, but I've only allocated three bits to the task in memory, because that's all I used to need. I'm going to have to shift the nine bits of y to the right by one, to make room for the larger x:

1100101010010

In a tiny program with only two variables, moving the memory around is not a big deal. But in a realistic program, which might have a million variables, you don't want to be moving memory around every time you change the value of a variable. That would be horrendously slow. We need a better strategy.

The standard way to deal with numerals of varying length is simply to force all numerals to have the same length, by padding them out with zeros. This fixed length is called the word size of the computer. For example, in my home I have several computers of various ages. Two of my computers store numbers as 32-bit words; on these computers, the 6 and 338 would be stored in memory as

0000000000000000000000000000011000000000000000000000000101010010

My newest computer uses 64-bit words, so that in memory the 6 and 338 look like

00000000000000000000000000000000000000000000000000000000000001100000000000000000000000000000000000000000000000000000000101010010

If I change x from 6 to 12, then the memory looks like this:

00000000000000000000000000000000000000000000000000000000000011000000000000000000000000000000000000000000000000000000000101010010

This extra padding is obviously wasteful of memory, but it provides a systematic way of storing numbers, which allows the computer to write and read numbers very quickly. When a variable's value is changed, we don't have to shift the rest of memory, to make room for that variable; we just have to alter the chunk where that variable is stored. That is, the system sacrifices some space efficiency for the sake of time efficiency. Space-vs-time tradeoffs are quite common in the design of computers and algorithms.

Overflow

For the sake of argument, suppose now that we're working on a 4-bit computer (such as the Intel 4004, which was state-of-the-art in 1971). Suppose that we want to add 9 = 1001₂ and 5 = 0101₂. (Notice that I've padded 101₂ out to four bits, since I'm on a 4-bit computer.) Here's the answer:

No problem; 1101₂ = 14 is the correct answer. But now suppose that we want to add 9 and 12 = 1100₂:

The answer 21 = 10101₂ cannot be stored in four bits; the answer has overflowed the word size of the computer. When this happens, the answer is truncated down to the word size. In our example, 10101₂ is truncated down to 0101₂.

Overflow is always a problem when doing numerical calculations on computers, but you and I don't run into it very often in our daily lives. This is because we typically use 32-bit computers, which overflow only when the numbers exceed 2³² - 1 = 4294967295, and we rarely do calculations with such large numbers. (A 64-bit computer will overflow even less often — only when a number exceeds 2⁶⁴ - 1 = 18446744073709551615.)

But what do we do, if we need to perform a calculation with extremely large numbers, that don't fit into our computer's word size? We have to adopt some more complicated system, such as representing large numbers as lists of word-size numbers and writing functions to perform arithmetic on large numbers represented as such lists. Python comes with this functionality built-in, and uses it automatically as it's needed. For example, there's no way I should be able to compute 2¹⁰⁰ on my 64-bit computer, but Python lets me:

>>> 2**21
2097152
>>> 2**100
1267650600228229401496703205376L

Notice the L at the end of the second result. This signals that the result is too large for the word size of the computer and is being handled by special algorithms for manipulating large numbers. For the most part we don't care that Python is handling large numbers in a special way; we just want it to give us the answers to all of our questions. But I can think of two reasons why Python should let us know. First, calculations that fit into the underlying computer's word size are handled by the underlying computer's arithmetic system, which is screamingly fast compared to the large-number algorithms. So we might care, if speed is an issue. Second, if we want to copy and paste the result into another program, such as a spreadsheet, then we should be aware that the other program might have problems handling such big numbers.

Disclaimer: The preceding discussion of word size has oversimplified several points and omitted many other points. However, for an introductory computer science that uses the Python programming language it's roughly what you need to know. If we were using the C programming language, for example, then we would have to go into memory issues in much greater detail. Essentially, Carleton teaches CS 111 using Python because Python lets us do interesting things without worrying about a lot of low-level issues.

Negative Numbers: Two's Complement

How can we represent negative numbers in a computer? Well, our Arabic numeral system represents negative numbers by preceding them with a negation sign "-"; the negation of 89 is -89. On paper, we can use similar notation for negative numbers in binary: the negation of 1010001₂ is -1010001₂. But deep inside a digital computer there isn't any symbol "-"; there are just bits. So in order to represent negative numbers in a computer, we need to represent "-" using bits somehow. Here's an idea. Let "+" be represented by the bit 0 and "-" by the bit 1. Then we can represent +89 and -89 as 01010001₂ and 11010001₂. This is called the sign bit system, because it reserves the first bit in a numeral for recording the sign.

The sign bit system is not crazy — one could build a computer this way — but nobody does, because there is a better way, called two's complement. In two's complement, numerals representing positive numbers (and 0) begin with 0, and numerals representing negative numbers begin with 1 — just as in the sign bit system — but the rest of the bits are organized very differently. The details depend on how many bits are in play — that is, on the word size of the computer. For the moment, suppose that we're working on a 4-bit computer.

To understand two's complement, start counting from 0 in binary. You can do this by starting at 0000₂ and repeatedly adding 0001₂, or by counting in decimal and converting decimal numerals to binary:

0000₂ = 0,
0001₂ = 1,
0010₂ = 2,
0011₂ = 3,
0100₂ = 4,
0101₂ = 5,
0110₂ = 6,
0111₂ = 7,
1000₂ = 8,
1001₂ = 9,
1010₂ = 10,
1011₂ = 11,
1100₂ = 12,
1101₂ = 13,
1110₂ = 14,
1111₂ = 15,
0000₂ = 0.

What happened at the end? We added 0001₂ to 1111₂. The answer overflowed and truncated back to 0000₂. We can view this as an error or as an opportunity. The opportunistic view is that 0000₂ is the number after 1111₂, so 1111₂ is the number before 0000₂. That is, 1111₂ is the number before 0. So 1111₂ must be -1. We just pulled negative numbers out of the air.

Continuing the idea, 1110₂ must be -2, because it is the number before -1, and 1101₂ must be -3, and so on. In fact, we can count back all the way to 0001₂ and decree that it is -15, or to 0000₂ and decree that it is -16. But standard practice is to push the negative numbers back only halfway through the sequence, so that all of the numerals starting with 1 represent negative numbers and all of the numerals starting with 0 represent nonnegative numbers.

To clarify: There are actually two ways to encode numbers into 4-bit words. The first way regards the binary numerals from 0000₂ to 1111₂ as encoding the numbers from 0 to 15; it is unable to represent any negative numbers. The second way regards the binary numerals from 0000₂ to 0007₂ as encoding the numbers from 0 to 7 and the binary numerals from 1000₂ to 1111₂ as encoding the numbers from -8 to -1. These two systems, called unsigned and two's complement, are summarized for 4-bit words in the following table.

Here is (some of) the corresponding table for 8-bit words:

Negation and Subtraction in Two's Complement

There is a simple procedure for computing the negation of a numeral:

1. Flip all of the bits; that is, change all 0s to 1s and all 1s to 0s.
2. Add 1 to the resulting number with truncation.

For example, with an 8-bit word size, 89 = 01011001₂, and we can compute -89 as

You can check this by adding 01011001₂ and 10100111₂; you get the 9-bit answer 100000000₂, which after truncation is the 8-bit numeral 00000000₂. This makes sense, because the sum of a number and its negation must be 0.

Subtraction is easy, once we have negation. To compute a - b, you simply compute -b and then add the result to a with truncation. This works because of the algebraic rule a + -b = a - b. For example,

Suppose now that we want to convert 11110110₂ to decimal. First we notice that 11110110₂ is negative, because the first bit is 1. If we negate it, we get

which is 10. Therefore 11110110₂ = -10.

By the way, the rule a + -b = a - b holds in two's complement only as long as no overflow occurs. If overflow occurs, then certain incorrect results show up, instead of the correct result. Also, this fundamental algebraic rule does not hold in the sign bit system at all; this is a major reason why the sign bit system is not used.

Conversion Between Binary and Hexadecimal (and Decimal)

Hexadecimal numerals are written not in base 10 or base 2 but in base 16. They require 16 different digits; to write in hexadecimal we need six more digits than we're used to. By convention, the six extra digits are A, B, C, D, E, F. The following table summarizes the conversion among binary, decimal, and hexadecimal for the numbers from 0 to 15.

Conversion from binary to hexadecimal is really easy: You just convert each block of four bits to the corresponding hexadecimal digit. For example,

1011001000001111₂ = 1011 0010 0000 1111₂ = B20F₁₆.

Similarly, to convert from hexadecimal to binary, you just expand each hexadecimal digit as four bits:

EB6A₁₆ = 1110 1011 0110 1010₂ = 1110101101101010₂.

Converting between base-2 and base-16 numerals is a lot easier than converting between base-2 and base-10 numerals. The reason is that 16 is a power of 2 — 16 = 2⁴, so four base-2 digits correspond perfectly to one base-16 digit — while 10 is not a power of 2, so there is no simple correspondence between decimal and binary digits.

There are two common approaches for converting base-10 numerals to base-16 numerals. First, you could expand the base-10 number as a weighted sum of powers of 16, and then read off the hexadecimal digits. For example,

Second, you could convert base-10 to base-2, and then base-2 to base-16. For example,

I usually follow the second approach, because I'm better at powers of 2 than powers of 16, and the extra step of converting binary to hexadecimal is not much work.

Floating-Point Numbers

Thus far we have talked exclusively about integers; we don't know anything about representing other real numbers such as 3.14159. In order to understand these numbers, consider this base-10 example:

The digits after the decimal point are simply coefficients on negative powers of 10. Now you can probably guess how to compute the binary expansion of 3.14159; you just need to use negative powers of 2. Here's a table of the first few.

Unfortunately, the binary expansion of 3.14159 requires infinitely many bits; I'll just show the first ten fractional bits.

Now we know how to write non-integer numbers as binary numerals. But how do we store these numerals as bits in a computer? The problem is that there is no "." inside the computer; there are just bits. To overcome this obstacle we use scientific notation. In scientific notation, a number is represented in three parts:

• a sign that indicates whether the number is positive or negative
• a significand or mantissa consisting of a single nonzero digit, followed by the fractional point ("."), followed by the fractional digits
• an exponent that indicates which power of the base the significand should be multiplied by.

For example, the numeral -73220.5 is written in base-10 scientific notation as -7.32205 * 10⁴. Here the sign is "-", the significand is "7.32205", and the exponent is "4". Similarly, the base-2 numeral 1011.01₂ is written in base-2 scientific notation as +1.01101₂ * 2³. For another example, 0.0111₂ is written as +1.11₂ * 2^-2. (The number 0 must be treated as a special case in scientific notation, because it has no nonzero digits at all.)

Many (but not all) computers in use today store floating-point numbers according to one of two binary formats, that are defined by the IEEE 754 standard. The single-precision format uses 32 bits:

• one bit to store the sign (0 for +, 1 for -)
• eight bits to store the exponent plus 127
• 23 bits to store the fractional part of the significand

The double-precision format uses 64 bits:

• one bit to store the sign (0 for +, 1 for -)
• 11 bits to store the exponent plus 1023
• 52 bits to store the fractional part of the significand

For example,

In single-precision floating point, this is stored as the 32-bit numeral

0 10000001 01110100000000000000000

The first bit indicates +, the next eight bits are the unsigned integer 129 (which is 2 plus 127), and the last 23 bits store the fractional part 011101₂ of the significand (with a bunch of trailing 0s). If you'd like to experiment with the floating-point representations of other numbers, try this automatic converter.

The IEEE 754 standard goes on to define how arithmetic operations are performed on numbers written on these formats. Because rounding is inevitable and can have serious (and subtle) effects on the results of calculations, there is extensive discussion in the standard of how and when to perform rounding in floating-point calculations. We will not cover the topic any more in this course.

Application: 24-Bit RGB Color

There are infinitely many different colors in the world, but experimental studies of human vision have determined that the human eye is sensitive to only about 10 million of them. The eye is not able to detect the difference between two minutely different shades of lime green, for example. Now consider how this might affect the design of a computer's graphics system. 10 million is less than 2²⁴, so 24 bits should be able to encode all of the different colors visible to the human eye.

As we have discussed in class, computers commonly represent colors as combinations of three primary colors, and the most prevalent primary system is Red Green Blue (RGB). So we want to store colors in 24 bits and we want to store colors in RGB format. The obvious solution to use eight bits for each channel R, G, and B. The unsigned integers that can be represented in eight bits are all of the integers between 0 and 255. So we end up measuring R, G, and B each on a scale of 0 to 255.

Recall that web pages are written in a language called HTML. In HTML, one can specify various colors on a web page: the background color of the page, the color of the text, the color of a particular feature on the page, etc. These colors are specified in HTML as 24-bit RGB colors, and they are written in hexadecimal rather than binary. That is, each channel is specified using two hexadecimal digits, for a total of six hexadecimal digits.

For an example, go to Wikipedia and view the page source. (In your web browser, this feature is probably in a menu called something like "View".) Search through this HTML for the word "background". You'll see an RGB color in hexadecimal. If you scroll down a little from there, you'll see more RGB colors. Try to figure out what each one represents on the page, by determining what color it is (e.g., pale green) and finding objects of that color on the displayed web page.

Storing RGB colors as 24-bit blocks doesn't align very well with the 32-bit word size of a typical computer. In fact, on many systems a 24-bit RGB color is actually stored as a 32-bit word. The eight extra bits essentially constitute a fourth channel of information, which is often called the alpha channel. An RGB color with an attached alpha channel is called an RGBA color. Sometimes the alpha channel is simply ignored; the eight bits are wasted. When it is not ignored, the alpha channel is frequently used to encode opacity. That is, an alpha value of 0 represents a completely transparent color, while an alpha value of 255 represents a completely opaque color. Software can use this extra opacity information to create interesting effects, such as the blending of one image into another.

In 3D computer graphics systems, it is common to measure each channel R, G, and B on a floating-point scale, from 0.0 to 1.0. How much memory is used if these floating-point numbers are single-precision? If they're double-precision? Either way, it's much more memory than the 24 bits that are theoretically sufficient. So why do 3D graphics systems use floating-point? It's because they do a great deal of computation with colors. For example, the final color of a 3D-rendered pixel may depend on the color of the object being rendered, the color of the virtual light in the scene, the angle at which the light is striking the surface of the object, and the angle at which the virtual camera is viewing the surface. These complicated calculations are more quickly and conveniently done in floating-point. In short, 3D graphics systems choose their RGB representation to favor time-efficiency over space-efficiency.