Binary Representation of Information

We depend on the concept of "POSITIONAL NOTATION" wherein the position of digits in a representation implies an association with a "POSITIONAL VALUE" - commonly called the Hindu-Arabic number system.

Contrast with the "Additive Notation" used in the Roman number system where each character represented a value, and the sum of the value representations determined the whole number.

Decimal Representation of integers

• In base 10 (decimal) notation, a positive integer x value is uniquely represented by k+1 decimal digits

dkdk-1...d1d0
where in a normalized representation:
dk is in the set {1,2,3,4,5,6,7,8,9}
di (belongs to) {0,1,2,3,4,5,6,7,8,9}, i=0 ,...., k-1

and the value associated with the representation can be computed by the formula:

x = dk10k + dk-110k- 1+....+d1101+d0100

• Examples:
14310  = 1·100 + 4·10 + 3·1

526110  = 5·103 + 2·102 + 6·101 + 1·100

Binary Representation of integers

• In base 2 (binary) notation, a positive integer x is uniquely represented by k+1 binary digits

dkdk-1...d1d0
where in a normalized representation:
dk = 1
di (belongs to) { 0 , 1 }, i=0 ,...., k-1

and the value associated with the representation can be computed by the formula:

x = dk2k + dk-12k- 1+....+d121+d020

• Examples:
1310  = 1·8 + 1·4 + 0·2 + 1·1
= 11012
6110  = 1·32 + 1·16 + 1·8 + 1·4+0·2 + 1·1
= 1111012

• Alternatively notice that

x = d0 + 2(d1+2(d2+.....+2(dk-1+2dk)...))

We will use both of these value expressions in developing the algorithms for number conversion.

NOTES:

• A normalized representation is does not include any "leading zeros" and thus the leftmost digit is always non-zero. In the case of a binary number system the leading digit is always 1, in decimal can be 1, ..., 9. However is a representation that uses a fixed number of digits (such as "8-bit") then it is necessary to add leading zeros to the left of the leftmost non-zero digit.

• If you look at the formulae for defining positional notations above you will find that it is quite feasible to have negative base values. There is quite a wealth of literature in Computer Science regarding the advantages of using a number system with a base of -2!
QUESTION: How many zeros are there to the left of the leftmost non-zero digit in ANY positional notation?

CS1104 Main Page
Last Updated 2001/09/17
© L.Heath, 2000, modified by J.A.N. Lee.