The following notes refer to material from Chapter 1.

Number Representation & Machine Memory:

Recall (see section 1.2) that machine memory is a collection of circuits each capable of storing a binary digit. Also, memory is usually organized into groups of eight (or sixteen, or thirty two etc.) bits (a word) each of which is given a unique address. It is the word size of the machine that determines, and limits, number representation.

Integer representation (section 1.6):

Positive and negative integers are represented in either excess or two's complement notation. To illustrate we assume a word size of four bits. We start with excess notation.

• Excess notation:
  1. Write down all bit patterns of length four in order from smallest to largest
  2. Let the pattern with 1 as the leftmost bit and 0 elsewhere represent 0₁₀
  3. Patterns starting with 1 will represent positive numbers and those starting with 0 negative numbers. That is, for this four bit system, 1001 will represent 1₁₀, 1010 will represent 2₁₀, etc. and, 0111 will represent -1₁₀, 0110 will represent -2₁₀, etc.

• Two's complement:

  The following procedure differs from that presented in the text and is presented here as a possibly simpler alternative.

  1. Reserve the leftmost bit for the sign with 0 indicating positive and 1 negative.
  2. For positive numbers the remaining bits will use the usual binary notation to represent numbers.
  3. To obtain negative numbers do the following:
     1. Take the bit pattern for each positive number.
     2. Flip (or complement) each bit.
     3. Use binary addition to add 1.
     The resulting bit patterns will represent the negative numbers corresponding to the associated positive numbers. That is, 0001 represents 1₁₀, but 1111 will represent -1₁₀. Similarly, 0011 represents 3₁₀, but 1101 will represent -3₁₀.

  The real benefit of two's complement is that it allows easy implementation of binary arithmetic. That is, binary addition and subtraction may be easily accommodated by designing an addition circuit only. To accomplish subtraction, merely represent the number to be subtracted in two's complement form and add.
  e.g. 4₁₀ - 6₁₀ may be written as 4₁₀ + (-6₁₀) = -2₁₀. In binary this becomes 0100 + 1010 = 1110

Notice that our four bit word system allows integers ranging from -8 to +7. In general, a k bit word will accommodate integers ranging from -2^k-1 to +2^k-1-1. For example, an 8 bit word would allow integers ranging from -128 to 127. Similarly, modern workstations, which have a word size of 32 bits, allow integers ranging from -2147483648 to +2147483647.

Practice problems:

See page 53 #1 and page 54 #2a, #2d and #2f.

Overflow: (page 51)

Since word size is fixed, it is possible that an addition or subtraction may lead to a result that is too large to be accommodated. For example, in our four bit system, 5₁₀ + 4₁₀ = 9₁₀ but in binary this becomes 0101 + 0100 = 1001. However, in two's complement, 1001 is NOT 9₁₀ but -7₁₀. This is the overflow problem. Similarly, -7₁₀ - 3₁₀ = -10₁₀. Using two's complement this becomes 1001 + 1101 = 0110. Notice that we discard the excess carry bit. However, in two's complement, 0110 is NOT -10₁₀ but 6₁₀.

Tip: Overflow only occurs when adding two numbers of the same sign. We may use this fact to help in determining if overflow has occurred. Merely examine the sign bit of the result of the addition. If it is different then overflow has occurred.

Floating-Point notation:

To represent scientific (or floating-point) notation in a fixed bit system we must decide how to partition the word into bits for the sign, exponent and mantissa. Also, since the exponent may be positive or negative, a representation scheme must be used for the exponent. Excess notation is typically used.

To illustrate, consider an eight bit word (Fig 1.24) where the leftmost bit is the sign bit, the next three bits the exponent bits and the remaining four bits the mantissa bits.

1. 2.75₁₀ = 10.11₂ = 0.1011 | 2
   Floating-point: 0 110 1011

2. -2.75₁₀ = - 10.11₂ = - 0.1011 | 2
   Floating-point: 1 110 1011

• Sign: 1 bit
• Exponent: 8 bits (excess notation)
• Mantissa: 23 bits (phantom bit trick)

• Sign: 1 bit
• Exponent: 11 bits (excess notation)
• Mantissa: 52 bits (phantom bit trick)

Truncation/Round-off Errors: (page 57)

Consider the case where we want to represent 2.625 in floating point notation using our eight bit scheme. Since 2.625₁₀ = 10.101₂ = 0.10101 | 2 then since we can accommodate at most four bits for the mantissa the floating-point representation is 0 110 1010. Observe that this is 2.5₁₀ and so we have introduced round-off error.

Practice problems:

See page 59 #1 and #2 (#1a, c, d and #2a, b, d will be solved in class).