Loading...

Binary Numbers Wolfgang Schreiner Research Institute for Symbolic Computation (RISC) Johannes Kepler University, Linz, Austria [email protected] http://www.risc.uni-linz.ac.at/people/schreine

Wolfgang Schreiner

RISC

Binary Numbers

Digital Computers Todays computers are digital. • Digital: data are represented by discrete pieces. – Pieces are denoted by the natural numbers: 0, 1, 2, 3 . . .

• Analog: data are represented by continuous signals. – For instance, electromagnetic waves.

Wolfgang Schreiner

1

Binary Numbers

Character Encodings • ASCII: American Standard Code for Information Interchange. – 128 = 27 characters (letters and other symbols). – Also non-printable characters: LF (line-feed). – Represented by numbers 0,. . . ,127. ASCII code ... 10 ... 48–57 ... 65–90 ... 97–122 ...

Wolfgang Schreiner

Character ... LineFeed (LF) ... 0–9 ... A–Z ... a–z ...

2

Binary Numbers

Character Encodings • Text is a sequence of characters. H i , H e a t h e r . 72 105 44 32 72 101 97 116 104 101 114 46 • ISO 8859-1 contains 256 = 28 characters (Latin 1). – First 128 characters coincide with ASCII standard.

• Unicode contains 65534 = 216 − 2 characters. – First 256 characters coincide with ISO 8859-1 standard.

The ASCII characters are the same in all encodings.

Wolfgang Schreiner

3

Binary Numbers

Binary Numbers In which number system are numbers represented? • Humans: decimal system. – 10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

• Computers: binary system. – 2 digits: 0, 1. – A bit is a binary digit. – Physical representation: e.g. high voltage versus low voltage.

Binary numbers are physically easy to represent.

Wolfgang Schreiner

4

Binary Numbers

Binary Numbers • Decimal number 103: 1 ∗ 102 + 0 ∗ 101 + 3 ∗ 100 = 1 ∗ 100 + 0 ∗ 10 + 3 ∗ 1 = 103.

• Binary number 1100111: 1 ∗ 26 + 1 ∗ 25 + 0 ∗ 24 + 0 ∗ 23 + 1 ∗ 22 + 1 ∗ 21 + 1 ∗ 20 = 1 ∗ 64 + 1 ∗ 32 + 0 ∗ 16 + 0 ∗ 8 + 1 ∗ 4 + 1 ∗ 2 + 1 ∗ 1 = 103

• Character g: ASCII code 103. Binary number 1100111 is computer representation of g.

Wolfgang Schreiner

5

Binary Numbers

Conversion of Binary to Decimal 1

0

1

1

1

0

1

1

0

1

1

1 1 + 2 × 1499 = 2999

Result

1 + 2 × 749 = 1499 1 + 2 × 374 = 749 0 + 2 × 187 = 374 1 + 2 × 93 = 187 1 + 2 × 46 = 93 0 + 2 × 23 = 46 1 + 2 × 11 = 23 1 + 2 × 5 = 11 1+2×2=5 0+2×1=2 1+2×0=1

Start here

Horner’s scheme. Wolfgang Schreiner

6

Binary Numbers

Conversion of Decimal to Binary Quotients

Remainders

1492 746

0

373

0

186

1

93

0

46

1

23

0

11

1

5

1

2

1

1

0

0

1

1 0 1 1 1 0 1 0 1 0 0 = 149210

Wolfgang Schreiner

7

Binary Numbers

General Number Systems • Any base value (radix) b possible. – Decimal system: b = 10. – Binary system: b = 2.

• n digits dn−1 . . . d0 represent a number m: m = dn−1 ∗ b n−1 + . . . + d0 ∗ b 0 =

P

0≤i

di ∗ b i .

• Number bounds: 0 ≤ m < b n . – Decimal system, 8 digits: 0 ≤ m < 108 = 100.000.000. – Binary system, 8 digits: 0 ≤ m < 28 = 256.

• Example: How many bit does it take to represent a character – in ASCII, in the ISO 8859-1 code, in Unicode? – n > logb m.

Wolfgang Schreiner

8

Binary Numbers

Other Number Systems • Octal system: – 8 digits 0, 1, 2, 3, 4, 5, 6, 7. – One octal digit (6) can be represented by 3 bits (110). – Conversion of binary number: 001100111: 001 100 111 1 4 7

• Hexadecimal system: – 16 digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. – One hexadecimal digit (B) can be represented by 4 bits (1011). – Conversion of binary number 01100111: 0110 0111 6 7

Easy conversion between binary and octal/hexadecimal numbers. Wolfgang Schreiner

9

Binary Numbers

Example Conversions Example 1 Hexadecimal Binary Octal

. B 6 0 0 0 1 1 0 0 1 0 1 0 0 1 0 0 0. 1 0 1 1 0 1 1 0 0 1 4 5 1 0 . 5 5 4 1

9

4

8

Example 2 Hexadecimal Binary Octal

C 4 . B 0 1 1 1 1 0 1 1 1 0 1 0 0 0 1 1. 1 0 1 1 1 1 0 0 0 1 0 0 7 5 6 4 3 . 5 7 0 4 7

B

A

3

Hexadecimal/octal numbers are shorter to write. Wolfgang Schreiner

10

Binary Numbers

Unsigned Binary Numbers Unsigned integers with n bits: from 0 to 2n − 1. Number 000 001 010 011 100 101 110 111

Unsigned Integer 0 1 2 3 4 5 6 7

Computer representation of finite-precision integers.

Wolfgang Schreiner

11

Binary Numbers

Signed Binary Numbers Signed integers with n bits: from −2n−1 to 2n−1 − 1. Number 000 001 010 011 100 101 110 111

Unsigned Integer Signed Integer 0 +0 1 +1 2 +2 3 +3 4 −4 5 −3 6 −2 7 −1

-4 -3 -2 -1 0 1 2 3 100 101 110 111 000 001 010 011

Two’s complement representation. Wolfgang Schreiner

12

Binary Numbers

Signed Binary Numbers Why this representation? • Arithmetic independent of interpretation. Binary: 010 + 101 = 111 Unsigned: 2 + 5 = 7 Signed: 2 − 3 = −1

• Computation of representation: – Determine representation of −3: – Representation of +3: 011. – Invert representation: 100. – Add 1: 101.

Simple implementation in arithmetic hardware. Wolfgang Schreiner

13

Binary Numbers

Binary Arithmetic Addend 0 0 1 1 Augend +0 +1 +0 +1 Sum 0 1 1 0 Carry 0 0 0 1

• Overflow: – Carry generated by addition of left-most bits is thrown away. – Addend and augend are of same sign, result is of opposite sign.

All hardware arithmetic is finite-precision.

Wolfgang Schreiner

14

Binary Numbers

Floating-Point Numbers How to represent 1.375? • Representation: (s, m, e) – the sign bit s denotes +1 or −1, – the mantissa m is a n bit binary number representing the value m/2n (< 1), – the exponent e is a binary number.

Value: s ∗ m/2n ∗ 2e • Example: Eight bit floating point: 0|01011|10 – the first bit 0 represents the sign +1, – the five bit mantissa 01011 represents the fraction 11/32 (why?), – the two bit exponent is 2.

Value: +1 ∗ 11/32 ∗ 22 = 1.375 Wolfgang Schreiner

15

Binary Numbers

Reals and Floating Points 3 Negative underflow 1 Negative overflow

—10100

5 Positive underflow 4 Zero

2 Expressible negative numbers

—10—100 0

6 Expressible positive numbers

10—100

7 Positive overflow

10100

• Example: fraction with 3 decimal digits, exponent with 2 digits. 1. Numbers between −0.999 ∗ 1099 and −0.100 ∗ 10−99. 2. Zero. 3. Numbers between 0.100 ∗ 1099 and 0.999 ∗ 1099.

• Real values are rounded to the closest floating point value. – Overflows and underflows may occur. Wolfgang Schreiner

16

Binary Numbers

Normalized Floating Point Numbers Example 1: Exponentiation to the base 2 2–2 –1

2

Unnormalized:

0 1010100

2–6 –5

2

.0

2–4 –3

2–8 –7

2

2–10 –9

2

2–12 –11

2

2–14 –13

2

2–16 –15

2

2

20 –12 –13 –15 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 = 2 (1 × 2 + 1 × 2 + 1 × 2

+ 1 × 2–16) = 432 Sign Excess 64 Fraction is 1 × 2–12+ 1 × 2–13 –15 –16 + exponent is +1 × 2 + 1 × 2 84 – 64 = 20 To normalize, shift the fr action left 11 bits and subtr act 11 from the e xponent.

Normalized:

0 1001001

1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 = 29 (1 × 2–1+ 1 × 2–2+ 1 × 2–4

.1

+ 1 × 2–5) = 432

Fraction is 1 × 2–1 + 1 × 2–2 +1 × 2–4 + 1 × 2–5

Sign Excess 64 + exponent is 73 – 64 = 9

Example 2: Exponentiation to the base 16 16–1

0 1000101

Unnormalized:

0 0 00

.

16–2

16–3

0 0 00

16–4 1 0 1 1 = 165 (1 × 16–3+ B × 16–4) = 432

0 0 01

Fraction is 1 × 16–3 + B × 16–4

Sign Excess 64 + exponent is 69 – 64 = 5

To normalize, shift the fr action left 2 he xadecimal digits , and subtr act 2 from the e xponent. Normalized:

0 1000011

Sign Excess 64 + exponent is 67 – 64 = 3

.

0001

1011

0000

0 0 0 0 = 163 (1 × 16–1+ B × 16–2) = 432

Fraction is 1 × 16–1 + B × 16–2

Left-most digit of mantissa is always non-zero. Wolfgang Schreiner

17

Binary Numbers

IEEE Floating-Point Standard 754 IEEE standard for floating point representation (1985). 1. Single precision: 32 bits (= 1 + 8 + 23). 2. Double precision: 64 bits (= 1 + 11 + 52). 3. Extended precision: 80 bits (inside hardware units only). Bits 1

8

23 Fraction

Sign

Exponent (a)

Bits 1

11

52

Exponent

Fraction

Sign (b)

Wolfgang Schreiner

18

Binary Numbers

IEEE Floating Point Characteristics Item Smallest normalized number Largest normalized number Decimal range Smallest denormalized number

Single Precision 2−126 2128 10−38 to 1038 10−45

Double Precision 2−1022 21024 10−308 to 10308 10−324

• Denormalized numbers: first bit of mantissa 0. – Distinguished from normalized numbers by 0 exponent. – Used to represent very small floating point numbers. – Avoid underflows by giving up precision of mantissa. – Smallest value: 1 in the rightmost bit, rest 0.

Wolfgang Schreiner

19

Binary Numbers

IEEE Numerical Types Normalized ±

0 < Exp < Max

Any bit pattern

Denormalized ±

0

Any nonzero bit pattern

Zero ±

0

0

Infinity ±

1 1 1…1

0

Not a number ±

1 1 1…1

Any nonzero bit pattern

Sign bit

• Two zeros (positive and negative). • Plus and minus infinity (overflows). • NaN (Not a Number = infinity / infinity).

Wolfgang Schreiner

20

Loading...