Chapter 1

  Bits, bytes, kilobytes and megabytes...

A bit is short for "binary digit." It is the smallest possible unit of information; i.e. a bit is to information what an atom is to an element! A bit could be represented by an on-off switch. This is essentially the case for static memory chips, or RAM (random-access memory), where each of the thousands of bits is a transistor, which may be in the on or off state. Dynamic RAM uses charged or uncharged capacitors to store data. [As an aside, static RAM is faster than dynamic RAM, but is also more expensive and power-consuming. Because capacitors discharge over time, dynamic memory must be constantly refreshed.] Magnetic media (floppies, hard drives, tape, even credit cards and ATM cards, use a positively or negatively charged magnetic region for each bit.

Data lines

Transferring individual bits between CPU and memory would be very time consuming, so it is customary to send a larger chunk of information. For some reason or another, memory is usually divided into eight-bit chunks called bytes. Four-bit chunks are called nibbles - no kidding! Most computers, then, will have at least 8 lines running between CPU and memory for data in and 8 lines for data out. Thus, a whole byte is transferred at once (in parallel). This also means that we only need a unique address for each byte in our memory, rather than having to have a unique address for each bit. Early IBM-type PCs had an 8-line (or 8-bit) data bus running between memory and the 8086 CPU. Later, the 80286 CPU improved on this by have a 16-bit data bus. Computers containing 80386, or 80486 have a 32-bit data bus. Pentium chips have a 64-bit external data bus.

We also have names for larger chunks of information. Since computers work in binary, memory is usually divided up into divisions that are a power of 2. Hence,

kilobyte = 1024 bytes (1024 = 2¹⁰), abbreviated KB (Kb is kilobits)

megabyte = 1024 KB = 1,048,576 bytes, abbreviated MB (Mb is megabits)

gigabyte = 1024 MB = 1,073,741,824 bytes, abbreviated GB (Gb is gigabits)

Address lines

Address lines run between the CPU and memory and are used to tell the memory which particular byte we want to read or write. Early microcomputers used 16 address lines. Each line could be [on/off; high/low; true/false; 0/1; etc.], allowing for 2¹⁶ unique addresses, or 65,536 bytes of addressable memory.

The original IBM PC had 20 address lines. Since 2²⁰ = 1,048,576, IBM PCs, and the Microsoft DOS which was written for it, could only utilize 1 MB of memory. About 360 KB was reserved for ROM BIOS, video RAM, etc. (more on this later), and the other 640 KB was available for the DOS operating system and user programs. PCs have essentially been stuck with that limitation ever since, although Windows (and other, newer, operating systems like OS/2, LINUX, Windows 95) gets around it somewhat. The CPUs themselves have advanced beyond that stage (the 80286 has 24 address lines, allowing for 16 MB to be addressed; the 80386/486 has 32 address lines to address 4 gigabytes), but in order to maintain "backward compatibility," DOS has remained a 1 MB (640 KB) world. Windows, and to a much greater extent, Windows 95, have crashed the 1 MB barrier by using protected mode, 32-bit addressing

So what do we put into memory?

Instructions and data!

Instructions

Instructions are stored as binary numbers, just as data is. For example, 10110010 (decimal 178) might be interpreted by the CPU as "get the byte of data located at the address given by the next two bytes and add it to the number in the accumulator (a part of the CPU that contains numbers to be acted on).

Data: ASCII, integers, floating point real and complex, etc.

To View ASCII Chart Go To DIGITAL BASICS

Data are usually either numbers or letters. Of course, memory can only hold binary numbers, so we have to agree how to interpret those numbers (a kind of code) when we want them to represent letters (or numbers, for that matter). ASCII stands for American Standard Code for Information Interchange. In this system, 7 bits are used to represent 128 (2⁷) different letters, numbers, punctuation, and special codes. When the eighth bit is used (why waste it?), we have Extended ASCII, in which 256 characters are available. The "upper" 128 characters are not as standard as the first 128. Refer to an Extended ASCII chart.

Not all computers use this system. IBM, on their mainframes, stubbornly sticks with EBCDIC, which means something but I have tried very hard to forget what. Unicode is a new system which use 2 bytes, allowing many more characters to be represented (how many, class?), such as Kanji, Cyrillic, Hebrew, etc. Unicode is backwards compatible with ASCII, meaning that operating systems using Unicode, such as Windows 95, can still make sense of ASCII files.

Earlier it was mentioned that 10110010 equals decimal 178. So why do we need a "code" for representing numbers in a computer? Why not just use binary (converted back to decimal when we type it in or read it, of course)? Well, how would we represent negative numbers? What about fractions? What about numbers larger than 8 bits can represent (2⁸ = 256)? You see the problem. The solution, shortened a bit (no pun intended) is to use more than one byte, and, for floating point numbers, to use some of the bits for an exponent and the rest for the mantissa. The table below shows some of the more common data types. The exact details depend on the particular program used (which, in turn, usually depends on the compiler used to create the program).

Data Type	Approximate Range		Significant
	(from)	(to)	Bits	Digits
logical	False (0)	True (1)	8	NA
character	a	Z (sort of!)	8	NA
short integer	-128.00	127.00	8	2
integer	-32,768	+32,767	16	4
long integer	-2 x 109	+2 x 109	32	9
single precision IEEE real	-3.4 x 10+38 to -1.2 x 10-38	+1.2 x 10-38 to +3.4 x 10+38	32	6
double precision IEEE real	-1.8 x 10+308 to -2.2 x 10-308	+2.2 x 10-308 to 1.8 x 10+308	64	15
single precision complex	like single precision real, for both real and imaginary parts	like single precision real, for both real and imaginary parts
double precision complex	like double precision real, for both real and imaginary parts	like double precision real, for both real and imaginary parts

Chapter 2

Breaking Down Binary Even Further

Table of Contents

• Basic Concepts Behind the Binary System
• Binary Addition
• Binary Multiplication
• Binary Division
• Conversion from Decimal to Binary
• Negation in the Binary System

Basic Concepts Behind the Binary System

To understand binary numbers, begin by recalling elementary school math. When we first learned about numbers, we were taught that, in the decimal system, things are organized into columns:

    H | T | O
    1 | 9 | 3

Years later, we learned that the ones column meant 10^0, the tens column meant 10^1, the hundreds column 10^2 and so on, such that

      10^2|10^1|10^0
        1 |  9 |  3 

As you know, the decimal system uses the digits 0-9 to represent numbers. If we wanted to put a larger number in column 10^n (e.g., 10), we would have to multiply 10*10^n, which would give 10^(n+1), and be carried a column to the left. For example, putting ten in the 10^0 column is impossible, so we put a 1 in the 10^1 column, and a 0 in the 10^0 column, thus using two columns. Twelve would be 12*10^0, or 10^0(10+2), or 10^1+2*10^0, which also uses an additional column to the left (12).

The binary system works under the exact same principles as the decimal system, only it operates in base 2 rather than base 10. In other words, instead of columns being

 
       10^2|10^1|10^0

        2^2|2^1|2^0

Instead of using the digits 0-9, we only use 0-1 (again, if we used anything larger it would be like multiplying 2*2^n and getting 2^n+1, which would not fit in the 2^n column. Therefore, it would shift you one column to the left. For example, "3" in binary cannot be put into one column. The first column we fill is the right-most column, which is 2^0, or 1. Since 3>1, we need to use an extra column to the left, and indicate it as "11" in binary (1*2^1) + (1*2^0).

Examples: What would the binary number 1011 be in decimal notation? 

Try converting these numbers from binary to decimal:

• 10
• 111
• 10101
• 11110

      2^4| 2^3| 2^2| 2^1| 2^0
         |    |    |  1  |  0
         |    | 1  |  1  |  1
      1  | 0  | 1  |  0  |  1
      1  | 1  | 1  |  1  |  0

Binary Addition

Consider the addition of decimal numbers:

     23
    +48
    ___

We begin by adding 3+8=11. Since 11 is greater than 10, a one is put into the 10's column (carried), and a 1 is recorded in the one's column of the sum. Next, add {(2+4) +1} (the one is from the carry)=7, which is put in the 10's column of the sum. Thus, the answer is 71.

Binary addition works on the same principle, but the numerals are different. Begin with one-bit binary addition:

    0    0    1
   +0   +1   +0
  ___  ___  ___  
    0    1    1

1+1 carries us into the next column. In decimal form, 1+1=2. In binary, any digit higher than 1 puts us a column to the left (as would 10 in decimal notation). The decimal number "2" is written in binary notation as "10" (1*2^1)+(0*2^0). Record the 0 in the ones column, and carry the 1 to the twos column to get an answer of "10." In our vertical notation,

    1
   +1
  ___
   10

The process is the same for multiple-bit binary numbers:

         1010
        +1111
       ______

• Step one:
  Column 2^0: 0+1=1.
  Record the 1.
  Temporary Result: 1; Carry: 0
• Step two:
  Column 2^1: 1+1=10.
  Record the 0, carry the 1.
  Temporary Result: 01; Carry: 1
• Step three:
  Column 2^2: 1+0=1 Add 1 from carry: 1+1=10.
  Record the 0, carry the 1.
  Temporary Result: 001; Carry: 1
• Step four:
  Column 2^3: 1+1=10. Add 1 from carry: 10+1=11.
  Record the 11.
  Final result: 11001

Alternately:

    11   (carry)
    1010
   +1111
  ______
   11001

Always remember

• 0+0=0
• 1+0=1
• 1+1=10

Try a few examples of binary addition:

       111      101      111
      +110     +111     +111
    ______    _____    _____

Binary Multiplication

Multiplication in the binary system works the same way as in the decimal system:

• 1*1=1
• 1*0=0
• 0*1=0

   101                      
  * 11
  ____
   101
  1010
 _____
  1111

Note that multiplying by two is extremely easy. To multiply by two, just add a 0 on the end.

Binary Division

Follow the same rules as in decimal division. For the sake of simplicity, throw away the remainder.

For Example: 111011/11

      10011 r 10
    _______
  11)111011
    -11
     ______
       101
       -11
     ______
        101
         11
     ______
         10

Decimal to Binary

Converting from decimal to binary notation is slightly more difficult conceptually, but can easily be done once you know how through the use of algorithms. Begin by thinking of a few examples. We can easily see that the number 3= 2+1. and that this is equivalent to (1*2^1)+(1*2^0). This translates into putting a "1" in the 2^1 column and a "1" in the 2^0 column, to get "11". Almost as intuitive is the number 5: it is obviously 4+1, which is the same as saying [(2*2) +1], or 2^2+1. This can also be written as [(1*2^2)+(1*2^0)]. Looking at this in columns,

        2^2 | 2^1 | 2^0
         1     0     1

What we're doing here is finding the largest power of two within the number (2^2=4 is the largest power of 2 in 5), subtracting that from the number (5-4=1), and finding the largest power of 2 in the remainder (2^0=1 is the largest power of 2 in 1). Then we just put this into columns. This process continues until we have a remainder of 0. Let's take a look at how it works. We know that:

   2^0=1
   2^1=2
   2^2=4
   2^3=8
   2^4=16
   2^5=32
   2^6=64
   2^7=128

Making this algorithm a bit more formal gives us:

1. Let D=number we wish to convert from decimal to binary
2. Repeat until D=0
   • a. Find the largest power of two in D. Let this equal P.
   • b. Put a 1 in binary column P.
   • c. Subtract P from D.
3. Put zeros in all columns which don't have ones.

1. Let D= the number we wish to convert from decimal to binary
2. Find P, such that 2^P is the largest power of two smaller than D.
3. Repeat until P<0
   • If 2^P<=D then
     • put 1 into column P
     • subtract 2^P from D
   • Else
     • put 0 into column P
   • End if
   • Subtract 1 from P

Now that we have an algorithm, we can use it to convert numbers from decimal to binary relatively painlessly. Let's try the number D=55.

• Our first step is to find P. We know that 2^4=16, 2^5=32, and 2^6=64. Therefore, P=5.
• 2^5<=55, so we put a 1 in the 2^5 column: 1-----.
• Subtracting 55-32 leaves us with 23. Subtracting 1 from P gives us 4.
• Following step 3 again, 2^4<=23, so we put a 1 in the 2^4 column: 11----.
• Next, subtract 16 from 23, to get 7. Subtract 1 from P gives us 3.
• 2^3>7, so we put a 0 in the 2^3 column: 110---
• Next, subtract 1 from P, which gives us 2.
• 2^2<=7, so we put a 1 in the 2^2 column: 1101--
• Subtract 4 from 7 to get 3. Subtract 1 from P to get 1.
• 2^1<=3, so we put a 1 in the 2^1 column: 11011-
• Subtract 2 from 3 to get 1. Subtract 1 from P to get 0.
• 2^0<=1, so we put a 1 in the 2^0 column: 110111
• Subtract 1 from 1 to get 0. Subtract 1 from P to get -1.
• P is now less than zero, so we stop.

Another algorithm for converting decimal to binary

However, this is not the only approach possible. We can start at the right, rather than the left.

All binary numbers are in the form

a[n]*2^n + a[n-1]*2^(n-1)+...+a[1]*2^1 + a[0]*2^0

Now we need to do the remaining digits. One idea is to "shift" them. It is also easy to see that multiplying and dividing by 2 shifts everything by one column: two in binary is 10, or (1*2^1). Dividing (1*2^1) by 2 gives us (1*2^0), or just a 1 in binary. Similarly, multiplying by 2 shifts in the other direction: (1*2^1)*2=(1*2^2) or 10 in binary. Therefore

{a[n]*2^n + a[n-1]*2^(n-1) + ... + a[1]*2^1 + a[0]*2^0}/2

is equal to

a[n]*2^(n-1) + a[n-1]*2^(n-2) + ... + a[1]2^0 

Let's look at how this can help us convert from decimal to binary. Take the number 163. We know that since it is odd, there must be a 1 in the 2^0 column (a[0]=1). We also know that it equals 162+1. If we put the 1 in the 2^0 column, we have 162 left, and have to decide how to translate the remaining digits.

Two's column: Dividing 162 by 2 gives 81. The number 81 in binary would also have a 1 in the 2^0 column. Since we divided the number by two, we "took out" one power of two. Similarly, the statement a[n-1]*2^(n-1) + a[n-2]*2^(n-2) + ... + a[1]*2^0 has a power of two removed. Our "new" 2^0 column now contains a1. We learned earlier that there is a 1 in the 2^0 column if the number is odd. Since 81 is odd, a[1]=1. Practically, we can simply keep a "running total", which now stands at 11 (a[1]=1 and a[0]=1). Also note that a1 is essentially "remultiplied" by two just by putting it in front of a[0], so it is automatically fit into the correct column.

Four's column: Now we can subtract 1 from 81 to see what remainder we still must place (80). Dividing 80 by 2 gives 40. Therefore, there must be a 0 in the 4's column, (because what we are actually placing is a 2^0 column, and the number is not odd).

Eight's column: We can divide by two again to get 20. This is even, so we put a 0 in the 8's column. Our running total now stands at a[3]=0, a[2]=0, a[1]=1, and a[0]=1.

We can continue in this manner until there is no remainder to place.

  Let's formalize this algorithm:
1.  Let D= the number we wish to convert from decimal to binary.
2.  Repeat until D=0:
    a) If D is odd, put "1" in the leftmost open column, and subtract 1 from D.
    b) If D is even, put "0" in the leftmost open column.
    c) Divide D by 2.
    End Repeat
For the number 163, this works as follows:
1.  Let D=163
2.  b) D is odd, put a 1 in the 2^0 column.
  Subtract 1 from D to get 162.
    c) Divide D=162 by 2.
Temporary Result: 01     New D=81
D does not equal 0, so we repeat step 2.

2.  b) D is odd, put a 1 in the 2^1 column.
  Subtract 1 from D to get 80.
     c) Divide D=80 by 2.
Temporary Result: 11     New D=40
D does not equal 0, so we repeat step 2.

2.  b) D is even, put a 0 in the 2^2 column.
    c) Divide D by 2.
Temporary Result:011    New D=20

2.  b) D is even, put a 0 in the 2^3 column.
    c) Divide D by 2.
Temporary Result: 0011     New D=10

2.  b) D is even, put a 0 in the 2^4 column.
    c) Divide D by 2.
Temporary Result:  00011      New D=5

2.  a) D is odd, put a 1 in the 2^5 column.
       Subtract 1 from D to get 4.
    c) Divide D by 2.
Temporary Result:  100011   New D=2

2.  b) D is even, put a 0 in the 2^6 column.
    c) Divide D by 2.
Temporary Result:  0100011   New D=1

2.  a) D is odd, put a 1 in the 27 column.
       Subtract 1 from D to get D=0.
    c) Divide D by 2.
Temporary Result:  10100011   New D=0

D=0, so we are done, and the decimal number 163 is equivalent to the binary number 10100011.

Since we already knew how to convert from binary to decimal, we can easily verify our result. 10100011=(1*2^0)+(1*2^1)+(1*2^5)+(1*2^7)=1+2+32+128= 163.

Negation in the Binary System

• Signed Magnitude
• One's Complement
• Two's Complement
• Excess 2^(m-1)

These techniques work well for non-negative integers, but how do we indicate negative numbers in the binary system?

Before we investigate negative numbers, we note that the computer uses a fixed number of "bits" or binary digits. An 8-bit number is 8 digits long. For this section, we will work with 8 bits.

The simplest way to indicate negation is signed magnitude. In signed magnitude, the left-most bit is not actually part of the number, but is just the equivalent of a +/- sign. "0" indicates that the number is positive, "1" indicates negative. In 8 bits, 00001100 would be 12 (break this down into (1*2^3) + (1*2^2) ). To indicate -12, we would simply put a "1" rather than a "0" as the first bit: 10001100.

In one's complement, positive numbers are represented as usual in regular binary. However, negative numbers are represented differently. To negate a number, replace all zeros with ones, and ones with zeros - flip the bits. Thus, 12 would be 00001100, and -12 would be 11110011. As in signed magnitude, the leftmost bit indicates the sign (1 is negative, 0 is positive). To compute the value of a negative number, flip the bits and translate as before.

Begin with the number in one's complement. Add 1 if the number is negative. Twelve would be represented as 00001100, and -12 as 11110100. To verify this, let's subtract 1 from 11110110, to get 11110011. If we flip the bits, we get 00001100, or 12 in decimal.

Using the regular algorithm for binary adition, add (5+12), (-5+12), (-12+-5), and (12+-12) in each system. Then convert back to decimal numbers.

Answers

  1011=(1*2^3)+(0*2^2)+(1*2^1)+(1*2^0)
      = (1*8) + (0*4) + (1*2) + (1*1)
  = 11 (in decimal notation)

10=(1*2^1) + (0*2^0) = 2+0 = 2
111 = (1*2^2) + (1*2^1) + (1*2^0) = 4+2+1=7
10101= (1*2^4) + (0*2^3) + (1*2^2) + (0*2^1) + (1*2^0)=16+0+4+0+1=21
11110= (1*2^4) + (1*2^3) + (1*2^2) + (1*2^1) + (0*2^0)=16+8+4+2+0=30

                      1                1
          111            111            111
         +110                  +110           +110
        ______               ______         _____
               1                      01          1101

           1                        11             1   
  101            101    101
        +111                  +111            +111
        _____                 ____           _____
              0                     00            1100

              1                    1                      1
     111    111          111
           +111                +111                 +111
          _____               _____                _____
         0                    10                 1110

Signed Magnitude:

    5+12         -5+12         -12+-5            12+-12 

 00000101       10000101       10001100        00001100
 00001100       00001100       10000101        10001100
__________      ________       ________        _________
 00010001       10010001       00010000        10011000

    17             -17            16              -24

One' Complement:

 00000101       11111010       11110011        00001100
 00001100       00001100       11111010        11110011
_________       ________       ________        ________
 00010001       00000110       11101101        11111111

    17             6              -18             0

Two's Complement:

 00000101       11111011       11110100        00001100
 00001100       00001100       11111011        11110100
 ________       ________       ________        ________
 00010001       00000111       11101111        00000000

     17            7              -17               0

Signed Magnitude:

 10000101       01111011       01110100        00001100
 10001100       10001100       01111011        01110100
 ________       ________       ________        ________
 00010001       00000111       11101111        01111100 

    109           119             111             124