DATA STORAGE IN COMPUTER

SYSTEM
Sadhana Jha
BITS Pilani Computer Science and Information Systems Department
BITS, Pilani
Pilani Campus
 Computer system, being a digital system, understands only 0 and
1
 0/1 denotes on/off
 Before storing in memory, data is converted to simple numbers
that are easy for a computer to store
 Each number is then reduced to a sequence of 0 and 1
 Numbers can be unsigned or signed
 Unsigned: 0∞
 Are stored in memory as it is
 E.g., 6  0 1 1 0, which is the binary representation of 6

 Signed: -∞  +∞
 0  +∞ is represented similar to the unsigned numbers
 -1  -∞ requires different way of storage
 Three ways to represent negative numbers:

 Sign magnitude

 1’s complement

 2’s complement

 Requirements to be met

 Subtraction using addition operation, i.e., X-Y = X + (-Y)

 No ambiguity

 Maximum use of bits

 Addition of binary bits

 0+0=0

 0+1=1

 1+0=1

 1 + 1 = 0 1 carry, in binary addition carry is discarded

 Subtraction of binary bits:

 0–0=0

 1–0=1

 1–1=0

 0 – 1 = 0 1  borrow
Sign Extension
 Increasing the number of bits of a binary number while
preserving the number's sign and value
• (73)10 = (1001001)2 = (01001001)2 after sign extension

• (-43)10 = (101011)2 = (11 101011)2 after sign extension

 Need for sign extension: To match the word size of the

processor
 Word: Minimum unit of data of a defined bit length that can
be addressed and moved between storage and
the computer processor
 Sign magnitude Representation
 0 in MSB represents +ve
 1 in MSB represents –ve
0 1 1 0  +6, 1 1 1 0  -6
 Range of representable values using N bits  [- 2N-1 -1 , +2N-1 -1]

 Whether requirements are met?

 1st Requirement: Consider +6 and -3:

0 1 1 0 (+6)

1 0 1 1 (-3)

1 0 0 0 1 (+1) + 6 – 3 ≠ +1, 1st requirement is violated

discarded

Note: For the ease of understanding, in this presentation we consider word

size = 4, therefore all the example uses four bits for representing values
 2nd requirement?

 1 bit is lost for sign representation

 32d requirement ?

 Consider representation of 0 in sign magnitude:

 +0  0 0 0 0

 -0  1 0 0 0 Ambiguity, 3rd requirement is violated

 1’s complement (1CT):

 0 in MSB represents +ve

 1 in MSB represents –ve

 1CT for a positive number is the number itself

 1CT of a negative number in N bits:

 1st Method: Subtract the number from [2N-1 -1]

e.g: -6 : 1 1 1 1 – 0 1 1 0 = 1 0 0 1

 2nd Method:

 Take the positive counterpart of the number

 Flip all its bits

e.g: -6 : 0 1 1 0  1 0 0 1
 Range of values using N bits is [- 2N-1 -1 , +2N-1 -1]

 1CT (1CT of -X) = +X, e.g., 1CT(1CT(-6)) = 1CT(1 0 0 1) = 0 1 1 0 (+6)

 Subtraction using 1CT:

1. Write the 1CT of the subtrahend

2. Add it to the minuend

3. If there is a carry over discard it and add 1 to the result

4. If there is no carry over, find the 1CT of the result and add –ve sign
before it
Consider 7 – 4:

1. 1CT (0 1 0 0) = 1 0 1 1

2. 0111

+ 1011

10010

3. 0010

+ 0001

0 0 1 1  +3
Consider 4 – 7

1. 1CT(7) = 1 0 0 0

2. 0100

+1000

1100

3. 1CT(1 1 0 0) = 0 0 1 1

4. Final answer is -ve of the result obtained i.e., 1 0 1 1  -3

Requirements met or not?

1. X-Y = X + 1CT(Y) (we have seen examples in previous two

slides)

- Overhead: 1 extra addition step

2. Loss of 1 bit for representing signs

3. Two values of zeros:

+0  0000

-0  1CT(0000)  1111
 2’s complement (2CT):

 0 in MSB represents +ve

 1 in MSB represents –ve

 2CT for a positive number is the number itself

 2CT of a negative number in N bits:

 1st Method: Subtract the number from [2N-1 -1] and then add +1

e.g: -6 : 1 1 1 1 – 0 1 1 0 = 1 0 0 1 + 0 0 0 1  1 0 1 0

 2nd Method:

 Take the positive counterpart of the number

 Flip all its bits and add +1 to the result

e.g: -6 : 0 1 1 0  1 0 0 1 + 1  1 0 1 0
 Range of values using N bits is [- 2N-1 , +2N-1 -1]

 2CT (2CT of -X) = +X, e.g.,

2CT(2CT(-6)) = 2CT(1 0 1 0) = 0 1 1 0 (+6)

 Subtraction using 2CT:

1. Write the 2CT of the subtrahend

2. Add it to the minuend

3. If there is a carry over discard it, the remaining bits gives the result

4. If there is no carry over, find the 2CT of the result and add –ve sign
before it
 Consider 7 – 4:

1. 2CT (0 1 0 0) = 1 0 1 1 + 0 0 0 1  1 1 0 0

2. 0111

+ 1100

1 0 0 1 1  +3

Discard
Consider 4 – 7

1. 2CT(7) = 1 0 0 0 + 0 0 0 1 = 1 0 0 1

2. 0100

+1001

1101

3. 2CT(1 1 0 1) = 0 0 1 0 + 0 0 0 1  0 0 1 1

4. Final answer is -ve of the result obtained i.e., 1 0 1 1  -3

Requirements met or not?

1. X-Y == X + 2CT(Y) (we have seen examples in previous two

slides)

- No overhead of 1 extra addition step

2. Although there is a loss of 1 bit for representing signs, 1 extra

value can be represented

3. No two values of zeros:

+0  0000

-0  2CT(0000)  1CT(0000) + 0001  1111 + 0001  0000  +0

The extra value in 2CT
-8 , -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, +8

 2CT(+8) = 1 0 0 0

 2CT(-8) = 1CT(1 0 0 0) + 0 0 0 1
 0 1 1 1 + 0 0 0 1  1 0 0 0 = 2CT(+8)
 To avoid the ambiguity about whether (1 0 0 0)2 should be considered as
2CT of +8 or -8 consider the following addition
1 0 0 0  2CT of either +8 or -8
+ 0 1 1 1  2CT(+7)
1 1 1 1  2CT(-1) , X + 7 = -1  X = -8
 2CT of X = -X ? prove.

 Effect of discarding carry in 1CT and 2CT addition.

 Overflow
 Only possible cases:
0 1 1 1 (+7) 1 1 1 1 (-1)
0 1 0 1 (+5) 0 1 1 1 (+7)
0 1 1 0 0 (- 4)  1 0 1 1 0 (+6)
Overflow Carry

1 0 1 0 (-6) 1 1 1 0 (-2)
1 0 0 1 (-7) 1 1 0 1 (-3)
1 0 0 1 1 (+3)  1 1 0 1 1 (-5)

Carry
Overflow
 Observations:
 When addition is performed on two numbers having same MSB
 When C3 ≠ C4

C4 =1 C3=0 C2=0C1=0C0=0 C4 =1 C3=1 C2=0C1=0C0=0

1 0 1 0 (-6) 1 1 1 0 (-2)
1 0 0 1 (-7) 1 1 0 1 (-3)
1 0 0 1 1 (+3) 1 1 0 1 1 (-5)

 Whenever an overflow occurs MSB gets modified

 Addition of two N bits integers B1 and B2 causes overflow only if
 B1 + B2 > +2N-1 – 1 and B1 + B2 < -2N-1 addition is
 Four different number systems:

 Binary base 2

 Octal base 8

 Decimal  base 10

 Hexadecimal  base 16
 Positional number system:

 Value of a digit in a number depends upon it’s position in the number

 Example:

 742 : 7 * 102 + 4 * 101 + 2 * 100 Value of 7 is 700

 472: 4 * 102 + 7 * 101 + 2 * 100  Value of 7 is 70

 247: 2 * 102 + 4 * 101 + 7 * 100 Value of 7 is 7

 Value of a number depends on the following:

 The digits in the number

 Position of the digits in the number

 Base of the number system

 Base: Gives the upper limit on the maximum character a number system
can have
 Base 2  0 – 1 (2 characters)

 Base 8  0 – 7 (10 characters)

 Base 10  0 -9 (8 characters)

 Base 16  0 – 9, A, B, C, D, E, F (16 characters)

Question?
 Computer understand which number system ?
 Why do we need other number systems?
Binary Number system
 0, 1 are the only allowed character

 Steps to represent a decimal number N in binary:

 Divide N by 2 and store the quotient

 Repeat step 1, until the number cannot be divided further

 E.g, ( 10 )10 = ( 0 1 0 1 0 )2

2 10
2 5 0
2 2 1 = (0 1 0 1 0)2
2 1 0
0 1
 Steps to convert binary to decimal number
 In a n-bit binary number weight of the positions are:
2n-1, 2n-2, 2n-3,..... 21, 20
 e.g1 : (0 1 0 1 0 1 1 0)2 =
(0*27 + 1*26 + 0*25 + 1*24 + 0*23 + 1*22 + 1*21 + 0*20)2
= (0 + 64 + 0 + 16 + 0 + 4 + 2 + 0)2
= (86)10

 e.g2 : (1 0 1 0 1 0)2
= (1*25 + 0*24 + 1*23 + 0*22 + 1*21 + 0*20)2
= (32 + 0 + 8 + 0 + 2 + 0)2
= (42)10
 Representation of real numbers using binary
 Real numbers: X.Y
 X – Similar to the way integers are represented (Explained in previous slides)

 Y

 Y * 2 = X’. Y’

 Store X’ and Y = Y’

 Repeat step 1 and 2, for the new fractional value obtained until X’.Y’ = 1.0

 Print all the value of X’.

Example - Convert 10.6875 to binary

(10)10 = (1010)2
(0.6875) 10 =
0.6875 * 2 = 1.375 -------- 1 = (1 0 1 0. 1 0 1 1)2
0.375 * 2 = 0.75 -------- 0
0.75 * 2 = 1.5 -------- 1
0.5 * 2 = 1.0 -------1
 Representation of floating point number into real numbers

 Binary number: X.Y

 X – Similar to the way integer values are obtained (Explained in

previous slides)

 Y

 Multiply each bit with the weight of its position, where weight of the
positions are: 2-1, 2-2, 2-3,.....

 Take the sum of the output

 E.g. 1 0 1 0 . 1 0 1 1

Integral part Fractional part

 1010 . 1011

 Integral Part : (1 0 1 0)2 = 1 * 23 + 0 * 22 + 1 * 21 + 0 * 20 = 10

 Fractional part: (1 0 1 1)2

= 1 * 2-1 + 0 * 2-2 + 1 * 2-3 + 1 * 2-4

= 1/2 + 0 + 1/8 + 1/16

= 0.5 + 0 + 0.125 + 0.0625

= 0.6875

(1 0 1 0 . 1 0 1 1)2 = (10.6875)10
 Conversion from Base r to decimal number
 (dn-1dn-2... d2d1d0)r = (dn-1×rn-1 + dn-2×rn-2 + ... + d1×r1 + d0×r0 )10, Where

d and n represents digits and their position in the number, respectively

 (A 1 C 2)16,

Digits (d) Position (n)

d0 = A = 10 n=3

d1 = 1 n=2
d2 = C n=1
d3 = 2 n=4

 Putting in above formula, 10×163 + 1×162 + 12×161 + 2 * 160 = (41410)10

 Conversion from decimal to Base r

 Use the repeated reminder/quotient method

 Conversion from Hexadecimal to decimal number

 (dn-1dn-2-3... d2d1d0)r = (dn-1×16n-1 + dn-2×16n-2 + ... + d1×161 + d0×160 )10

 E.g: (B 0 9 3)16

 d1 = B, d2 = 0, d3 = 9, d4 = 3

= 11×163 + 0×162 + 9×161 + 3 * 160

= (4243)10
16 261
 Conversion from decimal to Hexadecimal 16 5
16
 E.g: (261)10 = (105)16 16 1 0

0 1
 Conversion from Octal to decimal number

 (dn-1dn-2-3... d2d1d0)r = (dn-1×8n-1 + dn-2×8n-2 + ... + d1×81 + d0×80 )10

 E.g: (1073)16

 d1 = 1, d2 = 0, d3 = 7, d4 = 3

= 1×83 + 0×82 + 7×81 + 3 * 80

= (571)10

8 261
 Conversion from Decimal to Octal
8 32 5
 E.g: (261)10 = (405)8
8 4 0

0 4
 Binary to Octal Conversion

 Method 1

 Binary to Decimal

 Decimal to Octal

 Method 2

 Starting from the right-most bit (LSB), replace each group of 3

bits by the equivalent octal digit (add extra zeros to the left-most
bits, if necessary)
 (001110111)2 = (001)8 (110)8 (111)8 = (167)8

 (11101)2 = (011101)2 = (011)8 (101)8 = (35)8

only two bits One extra zero added

 Octal to Binary Conversion

 Method 1

 Octal to Decimal

 Decimal to Binary

 Method 2

 Convert each octal digit to a 3-digit binary number

 (167)8 = (001)2 (110)2 (111)2 = (001 110 111)2

 Binary to Hexadecimal Conversion

 Method 1

 Binary  Decimal  Hexadecimal

 Method 2

 Starting from the right-most bit (LSB), replace each group

of 4 bits by the equivalent octal digit (add extra zeros to

the left-most bits, if necessary)
 (111001110111)2 = (1110)16 (0111) 16 (0111) 16 = (E77) 16

 (11101)2 = (00011101)2 = (0001) 16 (1101) 16 = (1D) 16

only one bit three extra zeros added

 Hexadecimal to Binary Conversion

 Method 1

 Hexadecimal  Decimal  Binary

 Method 2

 Convert each octal digit to a 4-digit binary number

 (167)16 = (0001)2 (0110)2 (0111)2 = (000101100111)2

Fixed Point representation: Define a fixed point number type

simply by implicitly fixing the binary point to be at some

position of a numeral.

 Two parameters are required:

 width of the number representation (w)

 binary point position within the number (b)

 E.g., <8,3> representation of 11101101 will be 111.10101

 Floating Point Representation – IEEE 754 Standard

 Place of the decimal point is not fixed

 E.g. - 2.5 * 105 and +3.32 * 10-6

 Three pieces of information are required:

 Sign of the number (s)

 Significant value (m)

 Signed exponent of 10 (e)

 The data type float uses IEEE 32-bit single precision format and the data

type double uses IEEE 64-bit double precision format

 In single precision (32 bits):
 The MSB indicates the sign bit (s): 1 is -ve and 0 is +ve.
 The next 8 bits: Stores the value of the signed exponent (e)
 Remaining 23: Stores the significand also know as
mantissa (m).
 Value of a floating number IN 32 bits is

 e – 127: Excess 127 representation, meaning if the exponent

value is 5, it will be stored as 5 + 127 = 132 in the exponent
field
 If e is treated as an unsigned number

 The valid range of the exponents is 1 to 254, i.e.,

21 to 2254

 Values 00000000 and 111111111 are reserved to represent

special values

 If e is treated as an signed number

 The actual exponent is biased by 127 .i.e. the actual value of

the exponent is e − 127. This gives the range:

21 −127 to 2254 −127 = = 2 −126 to 2127.

Normalization: Representation of floating point numbers with
leading 1 bit
Excess 127: Subtraction of 127 from the exponent
Floating point representation of 0.5 in 32 bits =
0| 00000000 | 010000000……

Normalized representation of 0.5 in 3.2 bits =

1.0 * 2-1 = 0| 01111110 | 000000000……

exponent Mantissa

 1| 01010101 | 010100000……

exponent Mantissa

= (-1)-1 * 1.3125 * 2-42

= - 0.3125 * 2-42
 Why excess 127?

 Helps in natural ordering in the values stored in the exponent field

 Consider 2-126 and 2+126

 Case 1: In absence of Excess 127:

 -126 = 10000010

 +126 = 01111110

 While -126 is a smaller value the exponent field contains larger value
(10000010 > 01111110)

 Case 2: In presence of Excess 127:

 -126 is written as 1 (1 – 127 = 6)  00000001

 +126 is written as 253 (253 – 127 = 126)  11111101

 -126 is a smaller value and so is the value stored in the exponent (00000001 <
11111101)
Why normalization ?

 0 | 10000000 | 1 0 0 0 0….

= (-1)0 * 0.5 * 2128 - 127

= 0.5 * 21 (subtracting excess 127 from the exponent)

= 0.25 * 2 * 21

= 0.25 * 22 = 0.25 * 2129 (excess 127 format)

= 0 | 10000001 | 0 1 0 0 0 0…. (ambiguity, different representations

for same number)

 This can be avoided if the number is normalized

 Example: 1.5 * 21 != 0.15 * 22

 Represent a real number with an integer and a fraction part in
FP

 Convert and normalize the integer part into binary

 Convert the fraction part using the technique explained earlier

 Add the two results and adjust them to produce a proper final

conversion
 Example 1: 12.375
1. (12)10 + (0.375)10 = (1100)2 + (0.011)2 = (1100.011)2
2. Shift (1100.011)2 by 3 digits to normalize the value

(12.375)10 = (1.100011)2 * 23

s=0
Exponent = 130 (represented in excess 127)
Mantissa = 100011
FP Representation  0| 10000010 | 1000110000……
 Example 2: -105.625

1. (105)10 + (0.625)10 = (01101001)2 + (0.101)2 = (01101001.101)2

2. Shift (01101001.101)2 by 6 digits to normalize the value

(105.625)10 = (1.101001101)2 * 26

s = 1 (indicating the final value is negative)

Exponent = 133 (represented in excess 127, i.e., 133- 127 = 6)

Mantissa = 101001101 (extended to 23 bits)

FP Representation  1| 10000101 | 101001101….
 Five groups of single precision data can be represented using

IEEE 754 standard of FP representation:

 Five groups of double precision data can be represented using

IEEE 754 standard of FP representation: