1 of 26

CSC-105

​

​

Introduction to Computer Science

Lecture 2.2.

2 of 26

Alternative Number Systems

  • What if human beings had only four fingers on each hand?

​

​

  • Instead of basing our number system on ten, we would have probably had a number system based on eight

​

​

  • Such a number system is called octal or base eight

​

​

  • Just like in our decimal system (aka base 10) number system, we don’t have a symbol for ten, we would probably not have a symbol for eight or nine

3 of 26

Octal Number System

  • The way we count in the decimal system is 0, 1, 2, 3, 5, 6, 7, 8, 9 and then 10

​

  • The way we would count in the octal number system is 0, 1, 2, 3, 4, 5, 6, 7 and then?

​

    • We’ve run out of symbols

​

    • The only thing that makes sense is 10

​

  • In octal, the number that comes after 7 is 10

​

​

  • But the same symbol 10 now refers to a different quantity

​

​

  • In octal, 10 refers to the sum of fingers you have in

your new hands

​

4 of 26

Decimal vs. Octal System

​

Decimal system

Octal System

Number of dwarfs in Snow White

7

7

Fingers that cartoon characters have

8

10

Symphonies of Beethoven

9

11

Fingers that human have

10

12

Number of months in a year

12

14

Number of letters in the Latin alphabet

26

32

5 of 26

Decimal vs. Octal System

  • When we say the number of months in a year in octal is 14

​

  • To convert it into decimal, it is 8 + 4 = 12

​

  • When a two-digit octal number begins with something other than 1

​

    • For instance, number of letters in the Latin alphabet is 32,

​

    • You need to multiply the first digit with 8 and then add the second digit

​

= 32 (in octal)

​

= 3 * 8 + 2 (in decimal)

​

= 26 (in decimal)

​

6 of 26

Octal vs. Decimal System

Decimal System

  • The octal system isn’t different from the decimal system in any structural way.

​

​

  • It just differs in details

​

​

  • For example,

​

Each position in an octal number is a digit that’s multiplied by a power of eight

Octal System

7 of 26

Converting Octal to Decimal

  • Thus an octal number such as 3725 can be broken down like so:

​

3725 = 3000 + 700 + 20 + 5

​

  • The number can be expressed as the individual digits multiplied by the octal powers of eight:

​

3725 = 3 x 100 +

7 x 100 +

2 x 10 +

5 x 1

  • In decimal, it can be shown as:

​

3725 = 3 x 83 +

7 x 82 +

2 x 81 +

5 x 80

​

  • If you work this out in decimal, you’ll get 2005. This is how you convert from octal to decimal.

(Octal)

(Decimal)

(Octal)

8 of 26

9 of 26

Addition in Octal Number System

  • You can add and multiply octal numbers the same way you can multiply decimal numbers

​

  • The only real difference is that you use different tables for adding and multiplying individual digits

​

  • The addition table for octal numbers is given on the right.

​

  • For example, 5 + 7 = 14

​

  • Longer octal numbers can be added the same way as decimal numbers

10 of 26

Addition in Octal Number System

​

1 3 5 8

  • 6 4 3 8

​

11 of 26

Multiplication in Octal Number System

  • Similarly, 2 times 2 is still 4 in octal

​

  • But 3 times 3 isn’t 9

​

  • How could it be?

​

  • Insead 3 times 3, in octal, is 11

​

  • The entire multiplication table is given on the right

​

  • The table shows that 4 x 6 = 30, which is 24 in decimal

12 of 26

Number System for lobsters

  • Octal is as valid a number system as decimal.

​

  • But let’s go further

​

  • Now let’s develop a number system for lobsters

​

  • Lobsters don’t have fingers exactly, but they have pincers at the ends of their two long front legs

​

  • An appropriate number system for lobsters is base four

​

  • Counting in base four goes like this:

​

0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, ..... and so forth

13 of 26

Number System in Base Four

In base 4, the number 31232 can be written like this:

​

31232 = 3 x 10000 +

1 x 1000 +

2 x 100 +

3 x 10 +

2 x 1

31232 = 3 x 44 +

1 x 43 +

2 x 42 +

3 x 41 +

2 x 40

14 of 26

Number System for Dolphins

  • Suppose we were dolphins and must resort to using our two flippers for counting

​

  • This is the number system known as base two or binary (from the Latin for two by two)

​

  • It seems likely that we’d have only two digits and these would be 0 and 1

​

  • But no worries. Remember when we run out of single digits, the first two digit-number is always 10

​

  • In binary, we count like this:

​

0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001...

15 of 26

Decimal vs. Binary

​

Decimal system

Binary System

Number of heads that humans have

1

1

Number of flippers on a dolphin

2

10

Number of teaspoons in a tablespoon

3

11

Number of sides to a square

4

100

Number of fingers on one human hand

5

101

Number of legs on an insect

6

110

Number of days in a week

7

111

16 of 26

Binary System

  • In a multi digit binary system, the positions of the digits correspond to powers of two:

17 of 26

Binary System

  • So anytime we have a binary number composed of a 1 followed by all zeros, that number is a power of two, and the power is the same as the number of zeros

18 of 26

Converting from Binary to Decimal

101101011010 =

1 x 100000000000 +

0 x 10000000000 +

​

1 x 1000000000 +

​

1 x 100000000 +

​

0 x 10000000 +

​

1 x 1000000 +

​

0 x 100000 +

​

1 x 10000 +

​

1 x 1000 +

​

0 x 100 +

​

1 x 10 +

​

0 x 1

101101011010 =

1 x 211 +

​

0 x 210 +

​

1 x 29 +

​

1 x 28 +

​

0 x 27 +

​

1 x 26 +

​

0 x 25 +

​

1 x 24 +

​

1 x 23 +

​

0 x 22 +

​

1 x 21 +

​

0 x 20 = 2906

19 of 26

Converting from Base b to Decimal

dndn-1.... d1d0 =

dn x basen +

​

dn-1 x basen-1 +

​

dn-2 x basen-2 +

​

.

​

.

​

.

​

.

​

.

​

.

​

.

​

d1 x b1 +

​

d0 x b0 = Output

Input: An n-digit number in base b dndn-1....d1d0

​

where di represents the digit in ith place

​

and the first place (right most) is 0

​

​

Algorithm:

​

  • Multiply digit at ith place with b raised to the power of i

​

  • Add all of them up i.e.

​

  • ∑ni = 0 di x basei

20 of 26

Converting from Decimal to Binary

Input: 290610

​

Algorithm:

​

  • Keep dividing number by base 2 until you get 1

​

  • At any step, divide by quotient from previous step

    • Noting down the remainder from each step

​

​

2

2906

​

2

1453

0

2

726

1

2

363

0

2

181

1

2

90

1

2

45

0

2

22

1

2

11

0

2

5

1

2

2

1

​

1

0

21 of 26

Converting from Decimal to Binary

2

2906

​

2

1453

0

2

726

1

2

363

0

2

181

1

2

90

1

2

45

0

2

22

1

2

11

0

2

5

1

2

2

1

​

1

0

Input: 290610

​

Algorithm:

​

  • Keep dividing number by base 2 until you get 1

​

  • At any step, divide by quotient from previous step

    • Noting down the remainder from each step

​

​

Output: 1011010110102

22 of 26

Converting from Decimal to Base b

b

Input

​

b

Quotient 1

Remainder 1

b

Quotient 2

Remainder 2

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

b

Quotient n-3

Remainder n-3

b

Quotient n-2

Remainder n-2

b

Quotient n-1

Remainder n-1

​

Quotient n

Remainder n

Input: Input

​

Algorithm:

​

  • Keep dividing number by base b until you get a quotient < b

​

  • At any step, divide by quotient from previous step

    • Noting down the remainder from each step

​

​

Output:

​

Quotientn Remaindern Remaindern-1 .... Remainder1

23 of 26

Converting from Decimal to Binary

  • Converting from decimal to binary isn’t quite as straightforward, but here’s a template that lets you convert decimal numbers from 0 through 255 to binary

​

  • Let’s convert 150 in decimal to binary

24 of 26

Converting from Decimal to Binary

  • Converting from decimal to binary isn’t quite as straightforward, but here’s a template that lets you convert decimal numbers from 0 through 255 to binary

​

  • Let’s convert 150 in decimal to binary

25 of 26

Adding Binary Numbers

1 1 0 2

  • 1 1 1 2

​

26 of 26

Subtracting Binary Numbers

1 1 0 2

- 1 1 1 2

​