The Architecture of Computer Hardware and Systems Software

Chapter 4 Notes

NOTE: These notes omit two topics from the text: Nines complement and tens complement are not discussed.


4.1 UNSIGNED BINARY AND BINARY-CODED DECIMAL REPRESENTATIONS

UNSIGNED BINARY

Positive (unsigned) numbers are easy. Just use the base 2 number system. Using such a number system means that we can store numbers in the range 0000 0000 through 1111 1111 in a single byte (0 through 255). There is an obvious problem here. There aren't many applications where the only numbers required are integers in the range 0..255. Fortunately, this problem is easily solved: use more than one byte. In two bytes (16 bits), we can store numbers in the range 0000 0000 0000 0000 through 1111 1111 1111 1111 (0 through 65,535). In four bytes (32 bits), we can store numbers in the range 0 through 4,294,967,296 (that's too many 0's and 1's to type). However, there are still two problems, no matter how many bytes we use:

Fractions (usually called floating-point numbers) are discussed in here. However, there are several ways to represent negative numbers (but only one of these methods is commonly used on today's computers).

 


 

4.2 REPRESENTATIONS FOR SIGNED INTEGERS

No comment.

 


 

4.3 SIGN-AND-MAGNITUDE REPRESENTATION

This method is very simple. Just use the leftmost bit as a sign bit, with 0 representing a "+" and 1 representing a "-". Then the number +1 would be represented as 0000 0001, and -1 would be represented as 1000 0001 (we'll stick with 8-bit numbers to keep the examples simple). This method causes several problems, one of which is that there are two ways to represent the number 0! We have "positive" 0 represented as 0000 0000 and "negative" 0 represented as 1000 0000.

 


 

4.4 NINE'S DECIMAL AND ONE'S COMPLEMENT REPRESENTATION

I will not discuss nine's decimal representation. For a discussion, see the textbook.

The one's complement representation method represents positive numbers in the usual way, but negative numbers are represented by taking the positive representation and complementing (I use the term "flipping") each bit. Using this system, +2 is represented as 0000 0010, and -2 is represented as 1111 1101 (each bit is the opposite of the bits in +2). Note that with this method the leftmost bit is still a sign bit. The leftmost bit of all positive numbers will be 0 and the leftmost bit of all negative numbers will be a 1.

If you are given the ones complement representation of a negative number, you can easily determine its value by complementing each bit, determining the value of the complemented number, and putting a minus sign in front of the result.

 

EXAMPLE

Q. What does the ones complement number 1110 1111 represent in base 10?
A. This is obviously a negative number. To find its complement (positive value), flip each bit: 0001 0000. This number is +16. Therefore, the original number must have been -16.


 

EXAMPLE

Q. What number is this: 1111 1111?
A. Flip each bit: 0000 0000. This number is 0. Therefore the original number was negative 0! (This seems like it could be a problem)

 


 

EXAMPLE

Let's try some addition and subtraction problems and see how it works:

 +5 +5 0000 0101
 -+3 +-3 1111 1100
 ---- ---- ---------
 +2 +2 1)0000 0001 WRONG! (Ignore the carry bit)

The result (if you ignore the carry bit, which we will) is +1, when it should be +2 (off by 1).

 


 

EXAMPLE

Try another one:

 +10 +10 0000 1010
 -+ 6 +- 6 1111 1001
 ---- ---- ---------
 + 4 + 4 1)0000 0011 WRONG! (Ignore the carry bit again)

The result (if you ignore the carry bit again) is +3, when it should be +4 (off by 1I think I'm starting to see a pattern here).

 


 

EXAMPLE

Try one that should produce a negative answer:

 + 6 + 6 0000 0110
 -+10 +-10 1111 0101
 ---- ---- ---------
 - 4 - 4 1111 1011 RIGHT! This is the ones complement representation of -4!

 


 

One's complement appears to work OK if the result is negative, but it is off by 1 if the result is positive. This can be fixed by always adding the carry bit to your answer, but this then requires two additions. There is yet a better way.

 

4.5 TWOS COMPLEMENT NOTATION

The problem with a computer is that we have only a finite amount of space in which to represent numbers. Typical sizes are 8 bits, 16 bits, 32 bits, and 64 bits. The numbers that we can represent will be limited by how much space is available.

With 8 bits, 256 different numbers can be represented (28).

With 16 bits, 65,536 different numbers can be represented (216).

With 32 bits, it's 232, and with 64 bits, it's 264.

And, in each case, since we want to represent both positive and negative numbers, it makes sense that half should be positive and half should be negative.

However, the idea of representing numbers in a limited amount of space is not a new idea. We are all familiar with such an example in everyday life: a car's odometer. Let's look at the few numbers around 0:

...
00004
00003
00002
00001
00000
99999 (-1)
99998 (-2)
99997 (-3)
99996 (-4)
...

Where do the positive numbers meet the "negative" numbers? The most reasonable thing to do is to make half of the numbers positive and half of the numbers negative. Since there are 100,000 numbers, we can designate the first 50,000 (00000..49999) as positive numbers and the last 50,000 (50000..99999) as "negative" numbers. Obviously, addition will work for 2 positive numbers (as long as the result doesn't exceed 49999 -- we'll worry about this later). But what happens when you start using negative numbers?

 

EXAMPLE

Let's add a positive and a negative number:
 +2 00002
 +-3 99997
 --- -----
 -1 99999 (-1! it works!)

 


 

EXAMPLE

Let's add two negative numbers:
 -2 99998
 +-3 99997
 --- -----
 -5 1)99995 (-5! it works, if you ignore the carry bit.)

 


 

EXAMPLE

Now, do the same thing in binary (with only 4-bit numbers to keep it simple):

0111 (7)
0110 (6)
0101 (5)
0100 (4)
0011 (3)
0010 (2)
0001 (1)
0000 (0)
1111 (-1)
1110 (-2)
1101 (-3)
1100 (-4)
1011 (-5)
1010 (-6)
1001 (-7)
1000 (-8)

 

See if it works:

 +4 0100
 +-2 1110
 --- ----
 +2 1)0010 = +2!

 

Try another one:

 +2 0010
 +-4 1100
 --- ----
 -2 1110 = -2!

It appears to work! It also works with 8-bit numbers, 16-bit numbers, 32-bit numbers, or any-bit numbers! But how do you find the twos complement of a number? You do two things:


 

EXAMPLES

What value is 0001 0101 if it is interpreted as a twos complement number? This is obviously a positive number (note that the leftmost bit is still a sign bit; 0=positive and 1=negative). Its value is 1 + 4 + 16 = 21.

 

What does -21 look like? -21 and is formed by flipping every bit: 1110 1010. Then add 1 to this result: 1110 1010 + 1 = 1110 1011.

 

What value is 1010 1100 if it is interpreted as a twos complement number? This is a negative number. We need to find its opposite (a positive number) and then evaluate it using base two place values. To find its opposite, flip every bit: 0101 0011. Add 1 to this result: 0101 0011 + 1 = 0101 0100. This number is 4 + 16 + 64 = 84. Therefore the original number was -84.

 


 

BINARY-CODED DECIMAL (BCD)

Binary-coded decimal (BCD) simply involves storing each decimal digit as a binary number. The number 1234, for example, would be coded as a binary 1, a binary 2, a binary 3, and a binary 4. The binary equivalents of the 10 decimal digits are:

Decimal value

Binary value

4-bit Binary value

0

0

0000

1

1

0001

2

10

0010

3

11

0011

4

100

0100

5

101

0101

6

110

0110

7

111

0111

8

1000

1000

9

1001

1001

Since 4 bits are required to hold the largest digit, two decimal digits can be put into a single byte. This format is called packed decimal. While BCD involves slightly more processing, it is often used in business applications (COBOL uses a Binary-Coded Decimal format as its default) where calculations must be carried out to the penny, with no room for round-off errors.