Positional Number Systems

Number

Systems

Positional number systems

Whole numbers

Fractions

Accuracy

Concept of a Positional Number System

What does 4,752 (base 10) represent (in base 10)?

4 x 100040004 x 103

+7 x 1007007 x 102

+5 x 10505 x 101

+2 x 122 x 100

So what does 1011 (base 2) represent (in base 10)?

1 x 881 x 23

0 x 400 x 22

1 x 221 x 21

1 x 111 x 20

While this makes a nice definition, it is far too much work for "practical" use - binary numbers get to be long

Counting Revisited

DecimalBinaryOctalHexadecimal

0000

1111

21022

31133

410044

510155

611066

711177

81000108

91001119

10101012A

11101113B

12110014C

13110115D

14111016E

15111117F

16100002010

17100012111

18100102212

19100112313

20101002414

21101012515

22101102616

23101112717

24110003018

25110013119

2611010321A

2711011331B

2811100341C

2911101351D

3011110361E

3111111371F

321000004020

Faster Conversion of Binary to Decimal

Dibble-Dabble, Horner's Method, Algorithm 1.1

1. Start at the left, start with 0

2. Add in leading digit

3. If there's another digit, multiply total by 2, add in next digit, repeat this step until you reach the radix (binary) point.

Ex:11010 (binary) converted to base 10 is:

+ 1

x 2

+ 1

x 2

+ 0

x 2

+ 1

x 2

+ 0

Even Faster in Your Head

Ex:11010010110 (binary) converted to base 10 is:

(in your head 1,3,6,13,26,52,105,210,421,843,1686)

Which has just got to be a lot quicker than

1024

+ 512

+ 128

+ 16

+ 4

+ 2

(not even counting the time it takes to generate the powers of 2)

Fast Decimal to Binary Conversion

(Dibble-Dabble, Horner's Method, Algorithm 1.2)

Since all even numbers end in 0 (binary), and all odd numbers end in 1 (binary), and since division by 2 yields a 0 remainder for even numbers and a 1 remainder for odd numbers, the remainder after division by 2 gives you the LSB (least significant bit) of the corresponding binary number.

Just repeat this process until you get a 0 quotient

Ex: Convert 75 (decimal) to binary

2 | 75

2 | 37+1

2 | 18+1

2 | 9+0

2 | 4+1

2 | 2+0

2 | 1+0

0+1

Now, the trick to remember, the LSB is ON TOP, so read the answer from the bottom up:

75 (decimal) = 1001011 (binary)

Converting Other Bases

Ex: Convert 17 (base 9) to base 6.

Solution: First convert 17 (base 9) to base 10, using the first fast conversion algorithm:

Next, convert 16 (base 10) to base 6, using the second fast conversion algorithm:

6 | 16

6 | 2+4

0+2

Reading up, 17 (base 9) equals 24 (base 6), which both equal 16 (base 10)

Base 8 has a Special Relationship to Base 2

Conversion between octal and binary is particularly fast and trivial, if you are careful. Since 23 = 8, every 3 binary digits converts to 1 octal digit, but you have to start in the correct place - the radix point

The conversion is

0000

0011

0102

0113

1004

1015

1106

1117

Ex. Convert 10110011001111101000 to octal

Solution: starting at the RIGHT, block off into groups of 3

10|110|011|001|111|101|000

Now convert group-by-group to

2631750 (octal)

Conversion from octal to binary is even easier.

Ex. Convert 307125 to binary

Solution: 011|000|111|001|010|101, or, removing the dividing bars and the (useless for now) preceding 0, 11000111001010101

Hexadecimal to Binary

Hex to binary is just as quick and trivial, except, since 16 = 24, the binary numbers are grouped by 4's, and a longer conversion table needs to be "remembered"

Binary / Hexadecimal
0000 / 0
0001 / 1
0010 / 2
0011 / 3
0100 / 4
0101 / 5
0110 / 6
0111 / 7
1000 / 8
1001 / 9
1010 / A
1011 / B
1100 / C
1101 / D
1110 / E
1111 / F

Ex: Convert 1011010100001110101101010110011 to hex

Solution: 101|1010|1000|0111|0101|1010|1011|0011 converts to 5A875AB3 (hex)

Ex: Convert ACD01BF to binary

Solution: 1010110011010000000110111111

Binary Numbers in Real Machines

Real computers have a fixed length space for the storage of positive whole numbers in binary.

First question: How do we store numbers that are "too short to fit"?

Solution: Add preceding zeroes.

Ex: Show how 5 will be represented in 8 bits

Solution: 101 is only 3 bits long, so add 5 preceding zeroes to obtain 00000101

Ex: Show how 5 will be represented in 32 bits

Solution: 00000000000000000000000000000101

Second question: What is the largest number you can store this way in a fixed number of bits?

Solution: In binary it is all 1's, which is 1 less than 2 to the power of the number of bits!

Ex: What's the largest number that can be stored in 8 bits

Solution: 11111111 = 100000000 - 1 = 255

Third question: How many different numbers can be stored in a fixed number of bits?

Solution: 2 to the number of bits (all the combinations)

Ex: How many values can be stored in 8 bits

Solution: 256

Estimating Large Powers of 2

Most real computers frequently deal with larger collections of bits than 8. The VAX routinely handles 32 bits at a time (it prefers it to anything shorter), and can handle collections of 64, 128, and, on rare occasion, numbers than occupy 256 bits in length. How many combinations of these numbers are there?

Repeatedly multiplying by 2 to get the answer will take a long time - and is a waste of time.

Note: 210 = 1024 = 1K  1,000

Note: 220 = 210 x 210 = 1024 x 1024 = 1 Meg  1,000,000

Note: 230 = 210 x 210 x 210 = 1 Gig  1,000,000,000

250 would have 5 commas

2120 would have 12 commas

Now, all you need to do is get the LEADING DIGITS of the answer by looking at the power of two of the TRAILING DIGIT of the exponent

Ex: Estimate 236

Solution: 64,000,000,000

Ex: Estimate 245

Solution: 32,000,000,000,000

Ex: Estimate 2123

Solution: 8,000,000,000,000,000,000,000,000,000,000,000,000

Positional Number System for Values Less than 1

What does .475 (base 10) represent (in base 10)?

4 x 10-14 x .1.4

7 x 10-27 x .01.07

5 x 10-35 x .001.005

So what does .1101 (base 2) represent (in base 10)?

1 x 2-11 x .5.5

1 x 2-21 x .25.25

0 x 2-30 x .125.0

1 x 2-41 x .0625.0625

This is a totally unreasonable way of doing this conversion - and there is a way just as fast for fractionals as there is for whole numbers

Faster Conversion of Binary Fractions to Decimal

(Dibble-Dabble, Horner's Method, Extension of Algorithms 1.1 and 1.2)

1. Start at the right, start with 0

2. Add in the digit

3. Divide by 2

4. If there are more digits to the left, (but to the right of the binary point), go back to step 2

Ex: .1101 (binary) converted to base 10 is:

+ 1

2| 1

0.5

+ 0

2| 0.5

0.25

+ 1

2| 1.25

0.625

+ 1

2| 1.625

0.8125

Fast Decimal Fraction to Binary Conversion

(Horner's Method, Dibble-Dabble, Extension of Algorithms 1.1 and 1.2)

Use the "inverse" of the method used for integers

Note:

- if a number is between 1/2 and 1, then the first binary digit after the binary point is a 1

- otherwise , if the number is less than 1/2, the first binary digit is a 0.

Note:

- if we multiply the decimal number by 2, the whole number we get is the first binary digit after the binary point.]

Ex: Convert .40625 (decimal) to binary

.40625

0.8125

1.625

1.25

0.5

1.0

Now, the trick to remember is that the MSB is ON TOP, so read the answer from the top down:

.40625(decimal) = .01101 (binary)

Accuracy between Binary and Decimal

Note that 0.1 (decimal) does not come out evenly when converted to binary

0.2

0.4

0.8

1.6

1.2

0.4

0.8

1.6

1.2

0.4

...

.1 (decimal) = .0001100110011001100110011... (binary)

Also, .2, .3, .4, .6, .7, .8, and .9 are not exact

This poses a problem when trying to represent decimal fractions in a binary computer - always need to worry about accuracy

Accuracy Conversion

How many binary digits are necessary to represent a given decimal accuracy?

The proper relationship to examine is

If we know n, solve for m

So, to obtain 8 decimal place accuracy, we need 8/.3 = 26.7 bits of binary accuracy (in practice, we need at least 27 bits).

Remember quick power of 2 estimation:

3 decimal digits = 10 binary digits

So, going the other way, 60 binary digits will yield 20 decimal place accuracy.

Fundamentals of Computer Science1Number Systems