Chapter 3 - Number Systems

Other number systems

Octal (digits 0 to 7)

Group three binary digits together and represent as base 8.

Hexadecimal (digits 0 to 15, actually 0 to F)

Group four binary digits together and represent as base 16.

Hexadecimal-to-decimal conversion

Sum of powers method
Converts from least significant to most significant digit:

Multiply and add method
Converts from most significant to least significant digit:

Binary addition (unsigned)

Example:

               011110 <-- carries
               101101
             + 100111
overflow --> 1 010100

Hex addition

Add as if decimal numbers except:

if individual digits are A through F, convert to decimal equivalents and add
if sum is greater than 16, replace sum with sum minus 16 and carry 1
if sum is between 10 and 15 (decimal), replace sum with equivalent hexadecimal digit

  D         13
+ C   =   + 12
$19         25

carries  -->   1 1
               DF6D
             + 246C
overflow --> 1 03D9

Remember:

Example from the text of binary and hex addition

carries  -->   11111 
               111011
             + 100111
overflow --> 1 100010

carries  -->   1  1 
               11001
             + 01101
overflow --> 1 00110

               1235
             + 567A
no overflow --> 68AF

carries  -->   111  
               A9876
             + FDCA0
overflow --> 1 A7516

Fixed length binary numbers:

Computer arithmetic is performed on data stored in fixed length memory locations, typically 8, 16, or 32 bits.
No signed numbers (no sign bit)

An unsigned 8-bit binary number:

Example conversions between number systems:

decimal      binary        hex
    255      1111 1111      FF
     93      0101 1101      5D

Special problems occur in manipulating fixed length numbers.

decimal         binary          hex
    201   =     11001001   =     C9
  +  79   =   + 01001111   =   + 4F
    280   =   1 00011000   =   1 18
           overflow         overflow

The number 280 (base 10) is larger than the maximum 8-bit number; this results in a carry beyond 8 bits in the binary representation and a carry beyond two digits in the hexadecimal representation. When doing arithmetic using fixed length numbers, these carries are potentially lost.

How do you do negative numbers?

Signed magnitude
Use one bit for sign, 7 bits for number
Example: -1 (in an 8-bit system) could be 1000 0001 (base 2)

2's complement (most often used in computing)
Example: the 2's complement number representing -1 (in an 8-bit system) would be 1111 1111 (base 2)

What are complement numbers?

Consider odometer numbers on a bicycle:

Decimal examples

Odometer numbers are useful for both addition and subtraction (complements) of signed numbers.

- 2     + 998
+ 3     + 003
+ 1     1 001

In the second example, the correct result is just the +001; the overflow is ignored in fixed-length complement arithmetic.

Do subtraction as addition by using complements, i.e.
A - B = A + (-B)

Important: It is easier to compute -B and add than to subtract directly.

Example:

- 005     + 995
+ 003     + 997
+ 008     1 992

Note that 995 and 997 were added in the normal fashion, the overflow was ignored, and the result was 992, which can be converted from the complement (or odometer) system back to -8, the correct answer.

 signed   3-bit complement
     +3   003
     +2   002
     +1   001
      0   000
     -1   999
     -2   998
     -3   997
     -4   996
     -5   995
     -6   994
     -7   993
     -8   992

decimal   2's complement binary
   +127   01111111
   +126   01111110
   +125   01111101
    ...   ........
     +2   00000010
     +1   00000001
      0   00000000
     -1   11111111
     -2   11111110
    ...   ........
   -127   10000001
   -128   10000000

There are 256 numbers in an 8-bit fixed length 2's complement number system.
Why are these numbers called 2's complement?

M - N = M + (-N)
where -N is the complement of N.

Example:

decimal
    + 1   =     00000001
    - 1   =   + 11111111
      0   =   1 00000000

which does not equal 2^8, or 256; ignore the overflow, and the correct answer is zero.

Now we need an easy way to do 2's complement operations.

Example:

What is the representation of -27 (base 10) in 2's complement 8-bit notation?

  2^8 - 1     11111111
-      27   - 00011011
              11100100   corresponds to flipping all the bits;
                         also known as 1's complement
    add 1   + 00000001
   result     11100101   -27 in 2's complement representation

This approach is necessary because:

Fixed-length nature of numbers stored in a computer
More computationally efficient to implement a fast adder than an adder and a subtractor

Examples of 2's complement number operations

Addition and subtraction in 2's complement form

Addition: To compute N1 + N2, add N1 to N2
Subtraction: To compute N1 - N2, add N1 to -N2

Examples:

decimal        binary           hex
    11   =     00001011   =     000B
  + 21   =   + 00010101   =   + 0015
    32   =     00100000   =     0020

    21   =     00010101   =     0015
  - 11   =   + 11110101   =   + FFF5
    10   =     00001010   =     000A

    11   =     00001011   =     000B
  - 21   =   + 11101011   =   + FFEB
  - 10   =     11110110   =     FFF6

  - 11   =     11110101   =     FFF5
  - 21   =   + 11101011   =   + FFEB
  - 32   =   1 11100000   =     FFE0

How we got the 2's complements of -11 and -21:

 11     00001011
~11   - 11110100   1's complement
+ 1   + 00000001   add 1
-11     11110101   2's complement representation

Algorithm

Store N.
Obtain ~N, the 1's complement of N, by replacing (bit by bit) every 0 with a 1 and vice versa in the number's binary representation.
Add 1 and ignore any carry after the eighth bit.

Note: This algorithm works in hex by replacing each digit x with its hex complement, i.e. 15 - x. Example: The hex equivalent of 11 is $000B; its hex complement is then $FFF4, where each digit was computed as $F - x. Adding 1 to $FFF4 gives the result $FFF5 for the 2's complement of 11. (Using a dollar sign ($) before a number indicates that it is base 16.)

Example:

In binary:

 N     0000 0110 0100 0111
~N   - 1111 1001 1011 1000   1's complement
+1   + 0000 0000 0000 0001   add 1
-N     1111 1001 1011 1001   2's complement representation

In hex:

 N     0647
~N   - F9B8   1's complement
+1   + 0001   add 1
-N     F9B9   2's complement representation

A calculator will always give you the 2's complement directly.

The Most Significant Bit (MSB) is the binary digit corresponding to the largest power of 2 and is always 1 for a negative 2's complement number. As a result it is often called the sign bit.

In 2's complement, -0 = +0. Technically, 0 is the complement of itself.

 N     00000000
~N   - 11111111   1's complement
+1   + 00000001   add 1
-N     00000000   2's complement representation

Problems with fixed-length arithmetic

Overflow and underflow

For a 16-bit fixed-length number system,

Adding signed numbers can easily exceed these limits.

first digit
       0011   $3000
       0110   $6000
       1001   $9000

This result, from adding two positive numbers in the number system, results in $9000, which is larger than $7FFF, the largest allowed positive number. In fact, $9000 equals 1001 0000 0000 0000, which is a negative number. The sign of the result is different from that of the operands.

Rule: If there is a sign change in adding two positive 2's complement numbers, then overflow has occurred.

We can generalize these rules to signed addition and subtraction.

Sign extension

How about if numbers are of different length?

decimal   2's complement binary
          3-bit 4-bit  8-bit
     +3   011   0011   00000011
     +2   010   0010   00000010
     +1   001   0001   00000001
      0   000   0000   00000000
     -1   111   1111   11111111
     -2   110   1110   11111110
     -3   101   1101   11111101
     -4   100   1100   11111100

To extend a 2's complement number to a greater number of binary digits, you just continue the sign bit to the left.

Examples: Extend $9B to 16 bits.

$9B = 1001 1011 = 1111 1111 1001 1011 = $FF9B

Extend $5F to 16 bits.

$5F = 0101 1111 = 0000 0000 0101 1111 = $005F

Adding two 2's complement numbers of different length

43A0     43A0
  9B     FF9B   need to sign extend; you can't just add zeros.
????   1 433B

Note that the 8-bit $9B and the 16-bit $FF9B both represent -101 in their respective number systems.

Next Section: Chapter 4 - Introduction to Unix
Previous Section: Chapter 2 - Binary Numbers
EEAP 282 Class Notes Table of Contents