CPSC 121: Module 03 - Number Representation

CPSC 121: Module 03 - Number Representation

Overview of Number Representation

• Numbers can be represented as a sum of products.

• Each term consists of a digit multiplied by a power of a base.

Decimal Representation (Base 10)

• Digits range from 0 to 9.

• Commonly used due to humans typically counting with ten fingers.

• Example:

  • $219 = 2 imes 10^2 + 1 imes 10^1 + 9 imes 10^0 = 200 + 10 + 9$

Binary Representation (Base 2)

• Computers operate in binary because they recognize only two symbols: 0 and 1.

• Each binary digit (bit) corresponds to a power of 2.

• Notation for base: a subscript indicates the base of a number.

  • Example:

  • $11011<em>2 = 1 imes 2^4 + 1 imes 2^3 + 0 imes 2^2 + 1 imes 2^1 + 1 imes 2^0 = 27</em>{10}$

Other Number Bases

Hexadecimal Representation (Base 16)

• Includes digits from 0 to 9 and letters A to F (representing 10 to 15).

• Notation for hexadecimal includes a prefix 0x.

  • Example:

  • $0x3CF<em>{16} = 3 imes 16^2 + C imes 16^1 + F imes 16^0 = 3 imes 16^2 + 12 imes 16^1 + 15 imes 16^0 = 975</em>{10}$

• Purpose: making binary numbers more human-readable.

Conversion Between Bases

• Direct conversion between hexadecimal and binary is a standard practice.

• For binary to hexadecimal conversion, group binary bits into sets of four:

  • Example Grouping:

  • $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$

• If the total number of bits is not a multiple of four, leading zeros are added.

Binary to Decimal Conversion

• Process: Multiply each bit by the corresponding power of 2 and sum the results.

  • Example:

  • $11011<em>2 = 1 imes 2^4 + 1 imes 2^3 + 0 imes 2^2 + 1 imes 2^1 + 1 imes 2^0 = 27</em>{10}$

Decimal to Binary Conversion

• Find the largest power of 2 less than or equal to the number, subtract, and repeat until the sum equals the original number.

  • Example:

  • $27<em>{10} = 16 + 8 + 2 + 1 = 1 imes 2^4 + 1 imes 2^3 + 0 imes 2^2 + 1 imes 2^1 + 1 imes 2^0 = 11011</em>2$

Adding Binary Numbers

• Rules for binary addition resemble decimal addition:

  • 0 + 0 = 0

  • 1 + 0 = 1

  • 1 + 1 = 10 (carry over)

• Carry propagates to the next column.

• Example addition:

  • $11010 + 10010$

  • Carrying process demonstrated through binary digits.

Signed and Unsigned Integers

• Unsigned integers: Only represent non-negative integers.

• Signed integers: Use leftmost bit to indicate the sign (0 for positive, 1 for negative).

  • Example for sign magnitude:

    • Positive 21: $+21 = 010101_2$

    • Negative 21: $-21 = 110101_2$

Two's Complement Representation

• Negative numbers are represented by two's complement: invert bits and add 1.

• Example:

  • Two's complement of 11100010 = 00011101 + 1 = 00011110.

• Positive numbers have a leading zero; negative numbers have a leading one.

• Advantages: subtraction is achieved through addition of two's complements.

• Example: Subtraction as addition:

  • $x - y = x + (-y)$

  • Example of $x = 011011 (27<em>{10}), y = 001110 (14</em>{10})$ results in $001101 (13_{10})$.

Handling Two's Complement

• To reverse a two's complement operation, either flip and add 1 or subtract 1 and flip.

• All modern systems utilize two's complement for its simplicity and efficiency.

Real Numbers Representation

• Real numbers are expressed with both integer and fractional parts in binary.

• Integer part utilizes powers of 2 counting up, fractional parts count down from 2^{-1}.

  • Example:

  • $1011.1001 = 1 imes 2^3 + 0 imes 2^2 + 1 imes 2^1 + 1 imes 2^{-1} + 0 imes 2^{-2} + 0 imes 2^{-3}$

• Converting decimal reals to binary:

  1. Integer part conversion through division.

  2. Fractional part conversion via multiplication.

• Example with 13.90625:

  • Integer: 13 (binary: 1101)

  • Fraction: .90625 (binary: .11101)

  • Complete binary: 1101.11101

Scientific Notation in Binary

• Binary scientific notation uses powers of 2.

• Format: 1.xxxxx * 2^e where x is the mantissa and e is the exponent.

• Example:

  • $0.90625 = 1.1011100 imes 2^{0}$

• Important components for storage:

  • Exponent: a signed integer.

  • Mantissa: number after the decimal.

  • Sign: determines positivity or negativity.

Modular Arithmetic

• Classifying integers based on remainders after division by a number m.

• Notation for modulo: $r = x ext{ mod } m$ meaning remainder r when x is divided by m.

  • Example: $27 ext{ mod } 4 = 3$ (because 27 divided by 4 has a remainder of 3).

• Congruence relation: if two integers leave the same remainder when divided by m, they belong to the same equivalence classes.

  • Example: $55 ext{ mod } 4 ext{ is congruent to } 27 ext{ mod } 4$.

Fundamental Theorem of Modular Arithmetic

• If $a ext{ mod } m$ and $b ext{ mod } m$ are known, expressions with these can be simplified:

  • $ab ext{ mod } m ext{ and } a + b ext{ mod } m$ yield the same result whether mod is taken before or after operations.

• Example:

  • $((10 ext{ mod } 7) + (15 ext{ mod } 7)) imes (23 ext{ mod } 7)$ produces the same result as $(10+15) imes 23 ext{ mod } 7$.