Number Systems

CS205 Computer Organization and Architecture - Number Systems

Acknowledgments

• These materials are based on William Stallings' "Computer Organization and Architecture," 10th Edition.

• Corresponds to Chapter 9.

Chapter 02: Number Systems

Objectives

1. Understand basic concepts and terminology of positional number systems.

2. Explain techniques for converting between decimal and binary for integers and fractions.

3. Explain the rationale for using hexadecimal notation.

The Decimal System

• Based on decimal digits (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) to represent numbers.

• Example: 83 means eight tens plus three: $83 = (8 * 10) + 3$

• Example: 4728 means four thousands, seven hundreds, two tens, plus eight: $4728 = (4 * 1000) + (7 * 100) + (2 * 10) + 8$

• The decimal system has a base, or radix, of 10.

• Each digit in the number is multiplied by 10 raised to a power corresponding to that digit’s position.

  • $83 = (8 * 10^1) + (3 * 10^0)$

  • $4728 = (4 * 10^3) + (7 * 10^2) + (2 * 10^1) + (8 * 10^0)$

Decimal Fractions

• Same principle applies to decimal fractions, but negative powers of 10 are used.

• $0.256 = (2 * 10^{-1}) + (5 * 10^{-2}) + (6 * 10^{-3})$

• A number with both an integer and fractional part has digits raised to both positive and negative powers of 10.

  • $442.256 = (4 * 10^2) + (4 * 10^1) + (2 * 10^0) + (2 * 10^{-1}) + (5 * 10^{-2}) + (6 * 10^{-3})$

• Most significant digit:

  • The leftmost digit, carries the highest value.

• Least significant digit:

  • The rightmost digit.

Positional Interpretation of a Decimal Number

• Example:

  • 472.256

  • 4 is in the 100s place ($10^2$).

  • 7 is in the 10s place ($10^1$).

  • 2 is in the 1s place ($10^0$).

  • 2 is in the tenths place ($10^{-1}$).

  • 5 is in the hundredths place ($10^{-2}$).

  • 6 is in the thousandths place ($10^{-3}$).

Positional Number Systems

• Each number is represented by a string of digits in which each digit position $i$ has an associated weight $r^i$, where $r$ is the radix, or base, of the number system.

• The general form of a number in such a system with radix $r$ is: $(… a<em>3 a</em>2 a<em>1 a</em>0 . a<em>{-1} a</em>{-2} a<em>{-3} …)</em>r$

• The value of any digit $a<em>i$ is an integer in the range $0 < a</em>i < r$. The dot between $a<em>0$ and $a</em>{-1}$ is the radix point.

Positional Interpretation of a Number in Base 7

• Example:

  • Position 4: Value in exponential form is $7^4$, Decimal value is 2401.

  • Position 3: Value in exponential form is $7^3$, Decimal value is 343.

  • Position 2: Value in exponential form is $7^2$, Decimal value is 49.

  • Position 1: Value in exponential form is $7^1$, Decimal value is 7.

  • Position 0: Value in exponential form is $7^0$, Decimal value is 1.

  • Position -1: Value in exponential form is $7^{-1}$, Decimal value is 1/7.

The Binary System

• Only two digits, 1 and 0.

• Represented to the base 2.

• The digits 1 and 0 in binary notation have the same meaning as in decimal notation:

  • $0<em>2 = 0</em>{10}$

  • $1<em>2 = 1</em>{10}$

• To represent larger numbers, each digit in a binary number has a value depending on its position:

  • $10<em>2 = (1 * 2^1) + (0 * 2^0) = 2</em>{10}$

  • $11<em>2 = (1 * 2^1) + (1 * 2^0) = 3</em>{10}$

  • $100<em>2 = (1 * 2^2) + (0 * 2^1) + (0 * 2^0) = 4</em>{10}$

• Fractional values are represented with negative powers of the radix:

  • $1001.101<em>2 = 2^3 + 2^0 + 2^{-1} + 2^{-3} = 9.625</em>{10}$

Converting Between Binary and Decimal

• Binary notation to decimal notation:

  • Multiply each binary digit by the appropriate power of 2 and add the results.

• Decimal notation to binary notation:

  • Integer and fractional parts are handled separately.

Integers

• In binary notation, an integer represented by $b<em>{m-1}b</em>{m-2} … b<em>2b</em>1b<em>0$, where $b</em>i = 0$ or 1, has the value:

  • $(b<em>{m-1} * 2^{m-1}) + (b</em>{m-2} * 2^{m-2}) + … + (b<em>1 * 2^1) + b</em>0$

• To convert a decimal integer $N$ into binary form:

  • Divide $N$ by 2, obtaining a quotient $N<em>1$ and a remainder $R</em>0$. Then: $N = 2 * N<em>1 + R</em>0$, where $R_0 = 0$ or 1.

  • Divide the quotient $N<em>1$ by 2. Assume that the new quotient is $N</em>2$ and the new remainder is $R<em>1$. Then: $N</em>1 = 2 * N<em>2 + R</em>1$, where $R_1 = 0$ or 1.

  • So, $N = 2(2N<em>2 + R</em>1) + R<em>0 = (N</em>2 * 2^2) + (R<em>1 * 2^1) + R</em>0$

  • If $N<em>2 = 2N</em>3 + R<em>2$, then $N = (N</em>3 * 2^3) + (R<em>2 * 2^2) + (R</em>1 * 2^1) + R_0$

• Continued…

• Because $N > N<em>1 > N</em>2 …$, continuing this sequence will eventually produce a quotient $N<em>{m-1} = 1$ (except for the decimal integers 0 and 1, whose binary equivalents are 0 and 1, respectively) and a remainder $R</em>{m-2}$, which is 0 or 1.

  • Then $N = (1 * 2^{m-1}) + (R<em>{m-2} * 2^{m-2}) + … + (R</em>2 * 2^2) + (R<em>1 * 2^1) + R</em>0$, which is the binary form of $N$.

• Convert from base 10 to base 2 by repeated divisions by 2.

• The remainders and the final quotient, 1, give us, in order of increasing significance, the binary digits of $N$.

Fractions

• In binary notation, a number with a value between 0 and 1 is represented by $0.b<em>{-1}b</em>{-2}b<em>{-3} …$, where $b</em>i = 0$ or 1, and has the value:

  • $(b<em>{-1} * 2^{-1}) + (b</em>{-2} * 2^{-2}) + (b_{-3} * 2^{-3}) …$

• This can be rewritten as:

  • $2^{-1} * (b<em>{-1} + 2^{-1} * (b</em>{-2} + 2^{-1} * (b_{-3} + …)…))$

• To convert the number $F$ ($0 < F < 1$) from decimal to binary notation, we know that $F$ can be expressed in the form:

  • $F = 2^{-1} * (b<em>{-1} + 2^{-1} * (b</em>{-2} + 2^{-1} * (b_{-3} + …)…))$

• If we multiply $F$ by 2, we obtain:

  • $2 * F = b<em>{-1} + 2^{-1} * (b</em>{-2} + 2^{-1} * (b_{-3} + …)…)$

• From this equation, we see that the integer part of $(2 * F)$, which must be either 0 or 1 because $0 < F < 1$, is simply $b_{-1}$.

• So we can say $(2 * F) = b<em>{-1} + F</em>1$, where $0 < F<em>1 < 1$ and where $F</em>1 = 2^{-1} * (b<em>{-2} + 2^{-1} * (b</em>{-3} + 2^{-1} * (b_{-4} + …)…))$

• To find $b_{-2}$, we repeat the process. At each step, the fractional part of the number from the previous step is multiplied by 2. The digit to the left of the decimal point in the product will be 0 or 1 and contributes to the binary representation, starting with the most significant digit. The fractional part of the product is used as the multiplicand in the next step.

Examples of Converting from Decimal Notation to Binary Notation for Integers

• (a) 11 (Decimal notation)

  • 11 / 2 = Quotient 5, Remainder 1

  • 5 / 2 = Quotient 2, Remainder 1

  • 2 / 2 = Quotient 1, Remainder 0

  • 1 / 2 = Quotient 0, Remainder 1

  • $11<em>{10} = 1011</em>2$

• (b) 21 (Decimal Notation)

  • 21 / 2 = Quotient 10, Remainder 1

  • 10 / 2 = Quotient 5, Remainder 0

  • 5 / 2 = Quotient 2, Remainder 1

  • 2 / 2 = Quotient 1, Remainder 0

  • 1 / 2 = Quotient 0, Remainder 1

  • $21<em>{10} = 10101</em>2$

Examples of Converting from Decimal Notation to Binary Notation for Fractions

• (a) 0.81 (approximately)

  • 0.81 * 2 = 1.62, Integer Part 1

  • 0.62 * 2 = 1.24, Integer Part 1

  • 0.24 * 2 = 0.48, Integer Part 0

  • 0.48 * 2 = 0.96, Integer Part 0

  • 0.96 * 2 = 1.92, Integer Part 1

  • 0.92 * 2 = 1.84, Integer Part 1

  • $0.81<em>{10} = 0.110011</em>2$

• (b) 0.25 (exactly)

  • 0.25 * 2 = 0.5, Integer Part 0

  • 0.5 * 2 = 1.0, Integer Part 1

  • $0.25<em>{10} = 0.01</em>2$

Hexadecimal Notation

• Binary digits are grouped into sets of four bits, called a nibble.

• Each possible combination of four binary digits is given a symbol:

  • 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

• Because 16 symbols are used, the notation is called hexadecimal, and the 16 symbols are the hexadecimal digits.

• $2C<em>{16} = (2</em>{16} * 16^1) + (C<em>{16} * 16^0) = (2</em>{10} * 16^1) + (12_{10} * 16^0) = 44$

Table 2.3 Decimal, Binary, and Hexadecimal

Reasons for Using Hexadecimal Notation

• Not only used for representing integers but also as a concise notation for representing any sequence of binary digits.

• Reasons:

  • It is more compact than binary notation.

  • In most computers, binary data occupy some multiple of 4 bits, and hence some multiple of a single hexadecimal digit.

  • It is extremely easy to convert between binary and hexadecimal notation.

Summary

• The decimal system

• Positional number systems

• The binary system

• Converting between binary and decimal

  • Integers

  • Fractions

• Hexadecimal notation