CSc 116 notes

2) Number systems

Previous page Back      Next Previous page      Contents

Binary

The digital logic of computers is constructed from simple, reliable circuits that "lock" on one of two states, like a switch that flips from entirely on to entirely off. A computer consists mainly of AND, OR, and NOT gates. The two states of these devices can be interpreted as any pair of values, for example:
0 
1 
false 
true 
off 
on 
+ (plus) 
- (minus) 
To represent numbers, a single binary digit, or bit, can only represent 2 possible numbers, 0 or 1. If we want a greater range of numbers, we can add more bits to the number, giving the additional bits a place value, just as we do for ordinary decimal (base 10) numbers. Each additional bit doubles the number of possible combinations, so we have
number of bits 
possible  combinations 
      range  
2 
4 
0 .. 3 
3 
8 
0 .. 7 
4 
16 
0 .. 15 
8 
256 
0 .. 255 
To convert a binary number to decimal, one just adds up the place values of the 1-bits, as follows: 
Bit position    7 6 5 4 3 2 1 0                  7 6 5 4 3 2 1 0   try this one
Binary number   1 1 0 1 1 1 0 1                  1 0 1 0 0 1 1 0
                | |   | | |   |--->   1
                | |   | | +------->   4
                | |   | +--------->   8
                | |   +----------->  16
                | +--------------->  64
                +-----------------> 128
                                   -----
                                    221
This number has 8 bits. Note that I numbered them starting with 0 on the right, this way, the place value of each bit is 2 to the power of the bit number. For example, 2 to the 7th = 128.

7 computer scientists went for a walk. After a while, they counted themselves: 0, 1, 2, 3, 4, 5, 6. One must be missing! So they spent the rest of the day looking, but never figured out where the 7th one could have gone. This is known as an "off by one" error. It is all too common.

To convert from decimal to binary, one needs to divide by 2 repeatedly until 0 is reached. Then the remainders, reading up, are the binary number.

With a machine, we need to set aside a fixed number of bits to hold a number, common sizes are 16 or 32 bits. The number of bits chosen determines what range of numbers can be represented. Any bits over this amount will be lost. This sometimes leads to erroneous results.

Addition (and subtraction) of binary numbers is similar to ordinary addition. If the sum won't fit in one bit, you need to carry one to the next place on the left. The rules are:

Here is are some examples of addition: (the second illustrates a "ripple efect") 
    Carries-->  0 0 0 1  1 0 0          1 1 1 1  1 1 0
                1 0 1 0  1 1 0 0        0 1 1 1  1 1 1 1
              + 0 0 0 0  1 1 1 1        0 0 0 0  0 0 1 0
            ---------------------       ----------------
                1 0 1 1  1 0 1 1        1 0 0 0  0 0 0 1
Long binary numbers get hard for humans to read: 1100010010110101, 00001100110011001010101010101111
Besides, it takes a long time for us to convert such numbers into decimal. What we need is a more readable representation that is at the same time easy to convert to and from the binary bit pattern. Read on....

Hexadecimal

It is convenient to represent each group of 4 bits with a single digit, giving a base-16 representation of numbers, called hexadecimal or hex. We can associate with each group of 4 bits the corresponding numeric value, but there is one catch: after 9, we run out of normal digits, so we need single symbols for the values 10..15 [since 12 (base 16) = 18 (base 10)]. It is customary to use the letters A..F for this purpose. That gives us the following table relating binary to hexadecimal:
 
 F  1111 0000  0 
 E 1110 0001  1
 D 1101 0010  2
 C 1100 0011  3
 B 1011 0100  4
 A 1010 0101  5
 9  1001 0110  6
 8 1000 0111  7
This table can be used for hex addition, by counting around clockwise. When you pass the top, a carry is generated.
Similarly, to subtract, count counter-clockwise, if you pass the top, a borrow is needed.

Sample conversion between binary and hex: 

    0001 1010 0110 1110 1111 0101 1100 0111    (a 32 bit number)
     1    A    6    E    F    5    C    7
We will normally write this as 0x1a6ef5c7, 0x.. is the C convention for hex numbers.

Hex. addition examples

carries:                 1 1                1 1 1 1
        1 2 3 4            A B C D            F F F F
        5 0 6 7            E F 0 1            0 0 0 1
        -------            -------            -------
        6 2 9 B          1 9 A C E          1 0 0 0 0

Signed numbers (2's complement)

Unlike a piece of paper, a computer or calculator will be able to work with a fixed number of bits. Given a number of bits, there is a limit to the number of possible combinations of these bits. For example, if we work with 8 bits, there are 256 possible combinations. These may be used to represent 256 different characters, or the unsigned numbers from 0 to 255.
Any carry past the last bit will be discarded. This can lead to incorrect results. Most programs do not test for this. The best solution is to use more bits per number. With MIPS, we usually use 32.

If, however, we want to represent both positive and negative numbers, we need one bit to specify the sign, either - or +, so we must "steal" one of our 8 bits to use for the sign. It is useful to represent the positive signed numbers in the same way as their unsigned counterparts. This leads to the choice of the leftmost bit as the sign bit, and 0 for positive (1 for negative).

Using 8 bits, we can represent signed numbers in the range -128 .. +127

The interpretation of the last binary number as -83 seems surprising! But it follows from a desire to keep the arithmetic circuits as simple as possible:

2's complement operation for negating a number:

  1. Change every bit of the number (0 to 1, 1 to 0), this is the logical NOT operation on each bit.
  2. Add 1, giving the numeric negative.
This works for both positive and negative numbers. Here is an example, which discovers the proper value for 1010 1101 above:

binary hex decimal
Number 1010 1101 AD - ?
NOT 0101 0010 52
+ 1 0000 0001 01
Negated  0101 0011 53 + 83
Therefore, the proper value of 1010 1101 is - 83.

You can do this in either binary or hexadecimal. The hex digits in the hexadecimal table above are paired by their logical NOT partners. If the leftmost digit of a hex number is 8..F, the number is negative.

So in the example above, the complement of A is 5, and (since A is in the left column) the number is negative.

Subtraction using 2's complement and addition

Once a hardware designer has constructed addition circuits, it is not necessary to also build subrtaction circuits. It is only necessary to produce the 2's complement of the number to be subtracted, and then add. This works for both unsigned and signed numbers. Subtract instructions are always provided. This is how they are executed. It is normal for a final carry to be generated when two negative numbers are added, this carry is discarded. In any arithmetic, the result will be incorrect if the true result lies outside the range of representable numbers. There are also comparison instructions. These always give the right answer; the signed and unsigned versions use slightly different logic.

Prepared by Lin Jensen, Bishop's University, 9 January 1999. Last updated 11 February 2000.

Previous page Back      Next Previous page      Contents