Number

Systems

 

 

 

 

Positional number systems

Whole numbers

Fractions

Accuracy

Copyright 1993-95, Thomas P. Sturm

Concept of a Position Number System

 

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

4 x 1000 4000 4 x 103

+ 7 x 100 700 7 x 102

+ 5 x 10 50 5 x 101

+ 2 x 1 2 2 x 100

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

1 x 8 8 1 x 23

0 x 4 0 0 x 22

1 x 2 2 1 x 21

1 x 1 1 1 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

Decimal Binary Octal Hexadecimal

0 0 0 0

1 1 1 1

2 10 2 2

3 11 3 3

4 100 4 4

5 101 5 5

6 110 6 6

7 111 7 7

8 1000 10 8

9 1001 11 9

10 1010 12 A

11 1011 13 B

12 1100 14 C

13 1101 15 D

14 1110 16 E

15 1111 17 F

16 10000 20 10

17 10001 21 11

18 10010 22 12

19 10011 23 13

20 10100 24 14

21 10101 25 15

22 10110 26 16

23 10111 27 17

24 11000 30 18

25 11001 31 19

26 11010 32 1A

27 11011 33 1B

28 11100 34 1C

29 11101 35 1D

30 11110 36 1E

31 11111 37 1F

32 100000 40 20

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:

0

+ 1

1

x 2

2

+ 1

3

x 2

6

+ 0

6

x 2

12

+ 1

13

x 2

26

+ 0

26

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:

1

x9

9

+7

16

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

000 0

001 1

010 2

011 3

100 4

101 5

110 6

111 7

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-1 4 x .1 .4

7 x 10-2 7 x .01 .07

5 x 10-3 5 x .001 .005

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

1 x 2-1 1 x .5 .5

1 x 2-2 1 x .25 .25

0 x 2-3 0 x .125 .0

1 x 2-4 1 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

0

+ 1

2| 1

0.5

+ 0

2| 0.5

0.25

+ 1

2| 1.25

0.625

+ 1

2| 1.625

0.8125

 

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

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

x2

0.8125

x2

1.625

x2

1.25

x2

0.5

x2

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

.1

x2

0.2

x2

0.4

x2

0.8

x2

1.6

x2

1.2

x2

0.4

x2

0.8

x2

1.6

x2

1.2

x2

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.