Loading...

0

1

I S

1 0

1 0 S0

Department of Computer Science and Engineering, Indian Institute of Technology Bombay. Ashutosh Trivedi – 1 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Number-Base Conversions

Binary Arithmetic

Ashutosh Trivedi – 2 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Recap: Decimal Numbers – digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Ashutosh Trivedi – 3 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Recap: Decimal Numbers – digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. – How do we construct numbers greater than 9?

Ashutosh Trivedi – 3 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Recap: Decimal Numbers – digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. – How do we construct numbers greater than 9? – Use 0 and give convenient names to 10 (ten), 100 (hundred), 1000 (thousand), etc. and count with them. (examples).

Ashutosh Trivedi – 3 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Recap: Decimal Numbers – digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. – How do we construct numbers greater than 9? – Use 0 and give convenient names to 10 (ten), 100 (hundred), 1000 (thousand), etc. and count with them. (examples). – Convenient representation?

Ashutosh Trivedi – 3 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Recap: Decimal Numbers – digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. – How do we construct numbers greater than 9? – Use 0 and give convenient names to 10 (ten), 100 (hundred), 1000 (thousand), etc. and count with them. (examples). – Convenient representation? – Place-value system

The number 270 from a 9th century inscription in Gwalior, India [source] Ashutosh Trivedi – 3 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Recap: Decimal Numbers – digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. – How do we construct numbers greater than 9? – Use 0 and give convenient names to 10 (ten), 100 (hundred), 1000 (thousand), etc. and count with them. (examples). – Convenient representation? – Place-value system

The number 270 from a 9th century inscription in Gwalior, India [source]

– Examples: 270, and 7392, and 7392.56. Ashutosh Trivedi – 3 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Place-Value System

7392.56 = =

1 1 +6∗ 10 100 7 ∗ 103 + 3 ∗ 102 + 9 ∗ 101 + 2 ∗ 100 + 5 ∗ 10−1 + 6 ∗ 10−2 .

7 ∗ 1000 + 3 ∗ 100 + 9 ∗ 10 + 2 ∗ 1 + 5 ∗

Discussion: – Is there something special about having 10 digits? – Can we define arbitrary large numbers using fewer or more digits? – Examples: 1. 2. 3. 4.

1 Used

binary-digits = {0, 1} octal-digits = {0, 1, 2, 3, 4, 5, 6, 7} hexadecimal-digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} Sexagesimal-digits 1

as early as 3000 BC by Babylonians! Ashutosh Trivedi

Ashutosh Trivedi – 4 of 11 Lecture 2: Binary Numbers

Babylonian clay tablet YBC 7289

Babylonian clay tablet YBC 7289 with annotations. The diagonal displays an approximation of the square root of 2 in four sexagesimal figures, 1 24 51 10, which is good to about six decimal digits. [source]

Ashutosh Trivedi – 5 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Base-r Systems Let the digits of a base-r system be B = {0, 1, 2, . . . , r − 1}. A base-r number (an an−1 · · · a0 .a−1 a−2 · · · a−m )r where ai ∈ B is equal to decimal number: an ∗ rn + an−1 ∗ rn−1 + · · · + a1 ∗ r + a0 + a−1 r−1 + a−2 ∗ r−2 + · · · + a−m ∗ r−m . The following number-systems are important for this course. 1. Decimal System with decimal-digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 2. Binary System with binary-digits = {0, 1} 3. Octal System with octal-digits = {0, 1, 2, 3, 4, 5, 6, 7} 4. Hexadecimal System with hexadecimal-digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}

Ashutosh Trivedi – 6 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Base-r Systems Let the digits of a base-r system be B = {0, 1, 2, . . . , r − 1}. A base-r number (an an−1 · · · a0 .a−1 a−2 · · · a−m )r where ai ∈ B is equal to decimal number: an ∗ rn + an−1 ∗ rn−1 + · · · + a1 ∗ r + a0 + a−1 r−1 + a−2 ∗ r−2 + · · · + a−m ∗ r−m . The following number-systems are important for this course. 1. Decimal System with decimal-digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 2. Binary System with binary-digits = {0, 1} 3. Octal System with octal-digits = {0, 1, 2, 3, 4, 5, 6, 7} 4. Hexadecimal System with hexadecimal-digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} Let’s convert various numbers in different bases to decimal. – (4021.2)5 – (123.4)8 – (B44B)1 6 – (110101)2

Ashutosh Trivedi – 6 of 11

Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r.

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r. Examples: – What is 11 in binary?

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r. Examples: – What is 11 in binary? 11 =

(10 + 1)

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r. Examples: – What is 11 in binary? 11 = =

(10 + 1) ((5 ∗ 2) + 1)

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r. Examples: – What is 11 in binary? 11 =

(10 + 1)

=

((5 ∗ 2) + 1)

=

(((2 ∗ 2 + 1) ∗ 2) + 1)

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r. Examples: – What is 11 in binary? 11 =

(10 + 1)

=

((5 ∗ 2) + 1)

= =

(((2 ∗ 2 + 1) ∗ 2) + 1) ((((1 ∗ 2) ∗ 2 + 1) ∗ 2) + 1)

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r. Examples: – What is 11 in binary? 11 =

(10 + 1)

=

((5 ∗ 2) + 1)

= =

(((2 ∗ 2 + 1) ∗ 2) + 1) ((((1 ∗ 2) ∗ 2 + 1) ∗ 2) + 1)

=

(((((0 ∗ 2 + 1) ∗ 2) ∗ 2 + 1) ∗ 2) + 1)

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Question: Given a number in Decimal convert it into base-r. Examples: – What is 11 in binary? 11 =

(10 + 1)

=

((5 ∗ 2) + 1)

= =

(((2 ∗ 2 + 1) ∗ 2) + 1) ((((1 ∗ 2) ∗ 2 + 1) ∗ 2) + 1)

=

(((((0 ∗ 2 + 1) ∗ 2) ∗ 2 + 1) ∗ 2) + 1)

=

1 ∗ 23 + 1 ∗ 21 + 1

=

(1011)2 .

– What is 111 in octal? – General algorithm?

Ashutosh Trivedi – 7 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Examples: – What is 0.6875 in binary?

Ashutosh Trivedi – 8 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Examples: – What is 0.6875 in binary? 0.6875

=

1 (1 + 0.375) 2

Ashutosh Trivedi – 8 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Examples: – What is 0.6875 in binary? 0.6875

= =

1 (1 + 0.375) 2 1 1 (1 + (0 + 0.75)) 2 2

Ashutosh Trivedi – 8 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Examples: – What is 0.6875 in binary? 0.6875

1 (1 + 0.375) 2 1 1 = (1 + (0 + 0.75)) 2 2 = ··· 1 1 1 1 = (1 + (0 + (1 + (1 + 0)))) 2 2 2 2

=

Ashutosh Trivedi – 8 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Examples: – What is 0.6875 in binary? 0.6875

= = = = =

1 (1 + 0.375) 2 1 1 (1 + (0 + 0.75)) 2 2 ··· 1 1 1 1 (1 + (0 + (1 + (1 + 0)))) 2 2 2 2 (0.1011)2 .

– What is (0.513)10 in octal?

Ashutosh Trivedi – 8 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

How to do the converse? Examples: – What is 0.6875 in binary? 0.6875

= = = = =

1 (1 + 0.375) 2 1 1 (1 + (0 + 0.75)) 2 2 ··· 1 1 1 1 (1 + (0 + (1 + (1 + 0)))) 2 2 2 2 (0.1011)2 .

– What is (0.513)10 in octal? – What is (153.513)1 0 in octal? – General algorithm?

Ashutosh Trivedi – 8 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Octal and Hexadecimal Numbers Decimal 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

Binary 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Octal 00 01 02 03 04 05 06 07 10 11 12 13 14 15 16 17

Hexadecimal 0 1 2 3 4 5 6 7 8 9 A = 10 B = 11 C = 12 D = 13 E = 14 F = 15

– Notice that 23 = 8 and 24 = 16. – Converting between Octal and Binary, and Hex and Binary. Ashutosh Examples. Trivedi – 9 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Number-Base Conversions

Binary Arithmetic

Ashutosh Trivedi – 10 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Let’s generalize Decimal Arithmetic – Addition – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

Ashutosh Trivedi – 11 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Let’s generalize Decimal Arithmetic – Addition – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

– Subtraction – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

Ashutosh Trivedi – 11 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Let’s generalize Decimal Arithmetic – Addition – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

– Subtraction – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

– Multiplication – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

Ashutosh Trivedi – 11 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Let’s generalize Decimal Arithmetic – Addition – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

– Subtraction – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

– Multiplication – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

– Division – What do you need to remember? – What is the algorithm? – How to extend that in Binary?

Ashutosh Trivedi – 11 of 11 Ashutosh Trivedi

Lecture 2: Binary Numbers

Loading...