# Data Storage

The binary number system:

Computer arithmetic is different from the arithmetic that people use:

• Computers perform operations on numbers whose precision is finite and fixed.
• Computers represent numbers using the binary rather than the decimal system.

## 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
• print a 1.
Subtract this power of two from the number
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`
```0   1
1   2
2   4
3   8
4   16
5   32
6   64
7   128
8   256
9   512
10  1024```
Example: Print 481 in binary
Largest power below 481 is 256
481 >= 256 so print 1
481-256=225
225 >= 128 so print 1
225-128=97
97>=64 so print 1
97-64=33
33>=32 so print 1
33-32=1
1<16 so print 0
1<8 so print 0
1<4 so print 0
1<2 so print 0
1>=1 so print 1
Final string=111100001
To check: 1+32+64+128+256=481
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.

```#include <stdio.h>

void binary(int no) {
int powerof2=1;
while(powerof2*2<=no)   // Find largest power of 2
powerof2=powerof2*2; // less than or equal to no
do {
if(no >= powerof2) {
printf("1");      // Print a 1 in this position
no=no-powerof2;
}
else printf("0");    // Print a 0 in this position
powerof2=powerof2/2;
}
while(powerof2>0);
}

void main() {
int i;

for(i=0;i<1000;i++) { // Print all binary numbers
printf("\n %d = ",i);
binary(i);         // from 0 to 999
}
} ```
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.

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.
```#include <stdio.h>

void main() {
int i;

printf("%d = %x\n",i,i); // from 0 to 1000
} ```

## 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:

• Numbers larger than 999
• Negative numbers
• Fractions
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:
• 800+300=1200 - (too large)
• 300-700=-400 - (negative)
• 300/600=0.5 (not an integer)
For binary numbers the precision is usually 8,16,32 or 64.
```#include <stdio.h>

void main() {
int n;
unsigned char c=1;
unsigned short s=1;
unsigned int i=1;
unsigned long l=1;
unsigned long long ll=1;

for(n=1;(unsigned char)(c*2)>c;c=c*2,n++);
printf("unsigned char precision is %d \n",n);
for(n=1;(unsigned short)(s*2)>s;s=s*2,n++);
printf("unsigned short precision is %d \n",n);
for(n=1;(unsigned int)(i*2)>i;i=i*2,n++);
printf("unsigned int precision is %d \n",n);
for(n=1;(unsigned long)(l*2)>l;l=l*2,n++);
printf("unsigned long precision is %d \n",n);
for(n=1;(unsigned long long)(ll*2)>ll;ll=ll*2,n++);
printf("unsigned long long precision is %d \n",n);
}  ```
Notice that this program uses unsigned numbers, what happens if they are signed?