Lecture 1

Data Storage

The binary number system:

Computer arithmetic is different from the arithmetic that people use:

Binary Notation

When we write a number, we usually represent it using a string of digits between 0 and 9. The only reason for using 10 digits seems to be that we have ten fingers. Computers have no fingers and so are not as restricted!

A decimal number is constructed by summing multiples of the digits:

i.e. thousands, hundreds, tens, units - for a four digit decimal number.

e.g.    576=5*100+7*10+6*1

The number to multiply each digit by is 10d where d is the position of the digit (0 for units, 1 for tens etc..). The base for this power is called the Radix. When dealing with computers it is common to use radices other than 10. The most important radices are 2 and 16.

Information is most commonly stored in a digital computer as the presence or absence of a current, a charge or a magnetic field. It is uncommon to find a storage device that can store more than two levels. For this reason, it is very common to encounter radix 2 (or binary) numbers.

In binary, each digit can only be 0 or 1. A binary digit is called a bit. The columns in a binary number represent powers of 2.

i.e. sixteens, eights, fours, twos, units - for a five digit binary number.

Decimal
    Binary
0   0
1   1
2   10
3   11
4   100
5   101
6   110
7   111
8   1000
9   1001
10  1010
11  1011
12  1100
13  1101
14  1110
15  1111
16  10000
17  10001
18  10010
19  10011
20  10100
To convert between binary and decimal representations, use the following methods:

decimal to binary:

  1. Find the largest power of two that is less than or equal to the number.
  2. if the no is greater than or equal to this power of two
  3. otherwise
    1. print a 0.
  4. look at the next smallest power of two
  5. repeat from step 2 until there are no more powers of two left.
To do this quickly it is a good idea to know the small powers of two:
Powers of two
Example: Print 481 in binary To convert from binary to decimal, add the powers of two for each position in the binary number that is 1.

10011=1+2+16=19

Here is some C code to print a number in binary.

These notes contain example programs in C like the one above. If you are reading the notes online, then you can run the program by clicking on the "Run" button above. If you want to change the program, just modify the source code and Run it again.

Hexadecimal notation

Although binary numbers are common when dealing with machine representation of data, they are hard for human beings to work with. To provide a more compact representation, hexadecimal notation is used. Hexadecimal (or Hex) uses base 16, and the digits are:

0123456789abcdef

Decimal
    Binary
         Hex
0   0    0
1   1    1
2   10   2
3   11   3
4   100  4
5   101  5
6   110  6
7   111  7
8   1000 8
9   1001 9
10  1010 a
11  1011 b
12  1100 c
13  1101 d
14  1110 e
15  1111 f
One hex digit is four binary bits and so converting between hex and binary is simple.

010010101101

0100:1010:1101

4:a:d

This number is 4ad in hex.

38a=011:1000:1010=01110001010

Two hex digits are an 8 bit binary number 00,01,02..ff and can represent a decimal number from 0..255

Four hex digits are a 16 bit binary number and can represent a decimal number from 0..65535

In C, hexadecimal numbers have the prefix 0x and can be used in the same way as a decimal number.

e.g.

i=0x01f3e;
a=a+0x0100;
The 'printf' function allows you to print hexadecimal numbers directly using %x in the format string.
 
 

Finite precision numbers

When working out a calculation on paper by hand, there is always enough space to represent numbers. For a computer things are usually quite different. The amount of memory used for storing a number is fixed (in bits) at the time the machine is designed. It is possible to represent numbers larger than this fixed size but doing so will probably involve extra effort by the programmer. Numbers in a computer thus have a finite precision.

To think about finite precision numbers consider the set of positive integers that can be represented using three decimal digits. There are 1000 such numbers from 0..999, but this representation can not store:

When performing arithmetic operations on numbers it is important that the result is also a number. With finite-precision numbers this is not always the case: For binary numbers the precision is usually 8,16,32 or 64.
Notice that this program uses unsigned numbers, what happens if they are signed?