CS270 Colorado State University ===================== Number Representation ===================== Ch. 2 in book --------------------- Representing integers current number system based on Arabic characters and positional representation 93210 = 900 (9 hundreds) 30 (3 tens) 2 (2 ones) 10^2 10^1 10^0 ---- ---- ---- Common Bases Digits ------------ ------ Binary Octal Decimal Hexadecimal Base Conversions Decimal to Binary 55_{10} = ______________ _{2} Decimal to Hexadecimal 55_{10} = ______________ _{16} Decimal to Octal 55_{10} = ______________ _{8} 134_{10} = ______________ _{2} = ______________ _{8} = ______________ _{16} 6511_{8} = ? _{10} D49_{16} = ? _{10} ----------------------- How many numbers can N bits represent? base^N - what do each of the different combinations of digits mean? ----------------------- Unsigned Binary Numbers N = number of bits Range of numbers we can represent: 0 <= i <= (2^N - 1) - only positive values - all the bits determine the magnitude of the value ---------------- Signed Magnitude - sign bit determines sign (0 -- positive; 1 -- negative) - other bits determine magnitude N = number of bits Range of numbers we can represent: -(2^{N-1} - 1) <= i <= (2^{N-1} - 1) Problems - +0 and -0, end up only being able to represent 7 numbers with 3 digits - non-trivial algorithm for addition and subtraction ---------------- One's Complement - sign bit determines sign (0 -- positive; 1 -- negative) - if positive, other bits determine magnitude - if negative, complement all the bits to determine the magnitude - 1's complement operation = flip/toggle every bit - to convert a positive 1's complement value to a negative value perform a 1's complement operation - to convert a negative 1's complement value to a positive value perform a 1's complement operation N = number of bits Range of numbers we can represent: -(2^{N-1} - 1) <= i <= (2^{N-1} - 1) Problems - same as the signed magnitude problems ---------------- Two's Complement - sign bit determines sign (0 -- positive; 1 -- negative) - if positive, other bits determine magnitude - if negative, 2's complement all the bits to determine the magnitude - 2's complement operation = 1's complement operation + 1 - to convert a positive 2's complement value to a negative value perform a 2's complement operation - to convert a negative 2's complement value to a positive value perform a 2's complement operation N = number of bits Range of numbers we can represent: -2^{N-1} <= i <= (2^{N-1} - 1) Advantages - do not have to check sign to perform operations - only one representation for zero ----------------------- Representing Characters ASCII - 8 bits (1 byte) per character Unicode, UTF8 is type of this - 16 bits, superset of ASCII ---------- Operations (1) addition (2) logical operations ---------------------------- Addition with 2's complement sign extension - leading zeros do not change positive numbers - leading ones do not change negative numbers [do an example of 5 and -5, have students come up with 2's complement representation for both, 0101=00000101, 1011=11111011 (show the second is still true by performing 2's complement operation)] Performing addition 1644 0000 0110 0110 1100 + 826 +0000 0011 0011 1010 ------ ----------------------- 2470 Subtraction can be implemented as addition of a negative value 204 0000 0000 1100 1100 +-46 +1111 1111 1101 0010 ---- ----------------------- 158 overflow 7 0111 +5 +0101 --- ----- 12 1100 - Note that 12 is not in the representable range for 4-bit 2's complement 72 0100 1000 (8 bit example) +64 +0100 0000 --- ----------- 136 - We can detect overflow by comparing the C_{in} of the MSB with the C_{out} of the MSB. If they are different then there was an overflow. -------------------------- Bitwise logical operations Implementing truth tables. Representation of boolean values True = 1 False = 0 Common Operations: AND, OR, XOR, NOT ------------------------------------------------------------------------------- Review Questions (For use as a study aide) - For each of the bit representations, what is the minimal number of bits needed to represent the integers -X through Y? (where X and Y can be any integer) - With Z bits, what number range can you represent in each of the numeric representations? - Convert the number 0xZZZZ to binary, octal, and decimal representations for each possible bit representation. - What is the sum (or difference) between two numbers in any of the bit representations? - Give an example of overflow. Why does it happen? ------------------------ Copied and modified from Rick Ord's CS 30 notes and slides available with Patt book. mstrout@cs.colostate.edu, 8/27/08