=========================================== Assignment #03 - Data Representations =========================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com 1. Write down all the powers of two from zero ("1") to 16 ("65,536") showing their decimal values. Memorizing these powers of two will serve you well in Computer Science: 1 = 2**0 2 = 2**1 4 = 2**2 8 = 2**3 16 = 2**4 32 = 2**5 64 = 2**6 128 = 2**7 256 = 2**8 512 = 2**9 1024 = 2**10 2048 = 2**11 = 2**1 * 2**10 4096 = 2**12 = 2**2 * 2**10 8192 = 2**13 = 2**3 * 2**10 16384 = 2**14 = 2**4 * 2**10 32768 = 2**15 = 2**5 * 2**10 65536 = 2**16 = 2**6 * 2**10 2. Write down all the negative powers of two from -1 ("0.5") to -4 ("0.0625") showing their decimal and fractional (reciprocal) values: 0.5 = 2**-1 = 1 / 2**1 = 1/2 0.25 = 2**-2 = 1 / 2**2 = 1/4 0.125 = 2**-3 = 1 / 2**3 = 1/8 0.0625 = 2**-4 = 1 / 2**4 = 1/16 3. Write down all the powers of 16 from zero ("1") to 4 ("65,536") and relate each power of 16 to the corresponding power of two. 1 = 16**0 = (2**4)**0 = 2**0 16 = 16**1 = (2**4)**1 = 2**4 256 = 16**2 = (2**4)**2 = 2**8 4096 = 16**3 = (2**4)**3 = 2**12 65536 = 16**4 = (2**4)**4 = 2**16 4. Using a word size of four bits, list in order vertically all of the possible bit patterns from 0000(2) to 1111(2). Beside each of the 16 patterns, give: a) the hexadecimal equivalent of the bit pattern b) the unsigned decimal value of the bit pattern c) the four-bit signed-magnitude decimal value of the bit pattern d) the four-bit one's complement decimal value of the bit pattern e) the four-bit two's complement decimal value of the bit pattern You will create a small text table with 16 rows and five columns. Class Notes Reference: 060_different_binary_integers.html Note: I am not asking you to *convert* these bit patterns. I am asking you to tell me the decimal *value* of each bit pattern. The first row of the table (bit pattern 0000) will give (a) the hexadecimal digit for 0000, (b) the unsigned decimal value of 0000, (c) the sign-magnitude decimal value of 0000, (d) the one's complement decimal value of 0000, and (e) the two's complement decimal value of 0000. Look at the bit pattern and write its decimal value. BINARY |HEX |DEC |S/M |1's |2's 0000 0 0 0 0 0 0001 1 1 1 1 1 0010 2 2 2 2 2 0011 3 3 3 3 3 0100 4 4 4 4 4 0101 5 5 5 5 5 0110 6 6 6 6 6 0111 7 7 7 7 7 1000 8 8 -0 -7 -8 1001 9 9 -1 -6 -7 1010 A 10 -2 -5 -6 1011 B 11 -3 -4 -5 1100 C 12 -4 -3 -4 1101 D 13 -5 -2 -3 1110 E 14 -6 -1 -2 1111 F 15 -7 -0 -1 5. Why do computer programmers always start counting with zero (0), and not with one (1)? Arrays start at zero. The first element of an array is element zero. 6. The prefix used for a thousand Kilobytes is Megabytes. What is the prefix used for a thousand Gigabytes? Tera: GB * 1000 = TB (terabyte) = 10**12 (e.g. disk) If "thousand" is KiB, then GiB * KiB = TiB (tebibyte) = 2**40 (e.g. memory) 7. The prefix used for a thousand Kilobytes is Megabytes. What is the prefix used for a thousand Terabytes? Peta: TB * 1000 = PB (petabyte) = 10**15 (e.g. disk) If "thousand" is KiB, then TiB * KiB = PiB (pebibyte) = 2**50 (e.g. memory) 8. What is the difference between writing KB (kilobyte) and KiB (kibibyte) and MB (megabyte) and MiB (mebibyte)? a. KB (Kilobyte) = 1000 bytes = 10**3 bytes b. KiB (Kibibyte) = 1024 bytes = 2**10 bytes c. MB (megabyte) = 1000*1000 bytes = 1,000,000 bytes = 10**6 bytes d. MiB(mebibyte) = 1024*1024 bytes = 1,048,576 bytes = 2**20 bytes 9. What is the closest power of two to 1000 (i.e. closest to 10**3)? 1 K = 1000 (power of ten) = 10**3 1 Ki = 1024 (power of two) = 2**10 10. How many ns (nanoseconds) are in a ms (millisecond)? 1 ns = 1 * 10**(-9) 1 ms = 1 * 10**(-3) 1 ms / 1 ns = 10**(-3) / 10**(-9) = 10**6 = 1,000,000 = a million 11. How many KiB are in a GiB? 1 Ki = 2**10 1 Gi = 2**30 1 Gi / 1 Ki = 2**30 / 2**10 = 2**20 = 1,048,576 = Mi (power of two) 12. How many MiB are in a GiB? Give the answer as a power of two. 1 Mi = 2**20 1 Gi = 2**30 1 Gi / 1 Mi = 2**30 / 2**20 = 2**10 = 1024 = Ki (power of two) 13. Which of these measurements are powers of two, and which are powers of ten? a) Distances in kilometres? b) amount of hard disk capacity? c) amount of CDROM capacity? d) computer memory size? e) processor speed (clock frequency)? f) processor bus speed (e.g. PCI bus or front side bus or memory bus)? g) network card speed? h) dial-up modem speed? i) ADSL modem speed? j) Size of a file on your hard disk? Computer memory is always powers-of-two. File size may be either, depending on the program that displays size. All the rest are powers-of-ten. 14. Give two reasons why you can't store 8GB of system memory in a file on a hard drive with an advertised capacity of 8GB. 1. 8 GB of system memory is measured in powers-of-two GiB that is larger than powers-of-ten 8 GB of hard drive storage, i.e. 8 GiB = 8,589,934,592 bytes and 8 GB = 8,000,000,000 bytes. 2. The operating system needs to store name and directory information on the disk, as well as the data. That extra overhead takes space, so not all 8GB of the disk space are available for data. 15. What is 2**16 in decimal? See the list in Question 1. 65,536, a famous number in computer science 16. A computer has a 32-bit word size. Using this word size, what is the largest size memory it can address, in GiBi? (Microsoft Windows XP computers are limited to using this much memory.) How many items can 32 bits count? 2**32 2**32 = 2**2 * 2**30 = 4 GiB 17. By what order of magnitude (power of 10) is something that runs in nanoseconds (e.g. a CPU memory access) faster than something that runs in milliseconds (e.g. a hard disk access)? millisec / nanosec = 10**(-3) / 10**(-9) = 10**6 = six orders of magnitude (An "order of magnitude" is a power of ten; the answer is "six orders".) 18. Refer to the above answer. You have a program that takes 8 minutes to finish, running entirely in the computer's memory. With a bigger data set, you need to change the program to access the hard disk instead of memory. You change the program so that *all* accesses are via the slower hard disk. Roughly how long (in years) will it now take your "8-minute" program to finish? Computer memory is approximately a million (10**6) times faster than disk. The new program will be a million times SLOWER; it will run a million times LONGER. How long is eight minutes times a million? (8 minutes)*(million)/(minutes in a year) = = (8)*(10**6)/(60*24*365) = about 15.2 years to finish! 19. Exactly how many bytes (in decimal) are in 4GiB of memory? 4 GiB = 4 * 2**30 [a GiB is a power of two, not a power of ten] = 2**2 * 2**30 = 2**32 [add exponents] = 4,294,967,296 bytes 20. Exactly how many bytes (in decimal) are on an advertised 4GB hard disk? Disks are power-of-ten, not power-of-two. 4 GB = 4 * 10**9 = 4 * 1000 * 1000 * 1000 = 4,000,000,000 bytes 21. How many power-of-two TiB are on an advertised 1.5TB hard disk? Divide power-of-ten TB by power-of-two TiB: TiB = 2**40 [power of two] 1.5 TB = 1.5 * 10**12 [power of ten] 1.5*(10**12)/(2**40) = 1.364 TiB (not 1.5 TiB!) 22. By what percentage is a power-of-two GiB larger than a power-of-ten GB? Divide power-of-two TiB by power-of-ten TB: GiB = 2**30 = 1,073,741,824 GB = 10**9 = 1,000,000,000 GiB/GB = 1.073741824, so about 7.4% bigger 23. By what percentage is a power-of-two TiB larger than a power-of-ten TB? Divide power-of-two TiB by power-of-ten TB: TiB = 2**40 = 1,099,511,627,776 TB = 10**12 = 1,000,000,000,000 TiB/TB = 1.099511627776, so about 9.95% bigger 24. Which has more space, a 2 TB disk or a 1.8 TiB disk? Compare power-of-two TiB with power-of-ten TB: 2TB = 2 * 10**12 = 2000000000000 1.8TiB = 1.8 * 2**40 = 1979120929996.8 <- a little bit smaller 25. How many power-of-two MiB are on an advertised 2TB hard disk? How many power-of-two GiB are on an advertised 2TB hard disk? How many power-of-two TiB are on an advertised 2TB hard disk? Divide power-of-ten TB by power-of-two TiB: 2TB disk = 2,000,000,000,000 = 2*(10**12) bytes 1 MiB = KiB * Kib = 2**10 * 2**10 = 2**20 bytes 2*(10**12)/(2**20) = 1,907,348.633 MiB 2TB disk = 2,000,000,000,000 = 2*(10**12) bytes 1 GiB = KiB * KiB * KiB = 2**30 bytes 2*(10**12)/(2**30) = 1,862.645 GiB 2TB disk = 2,000,000,000,000 = 2*(10**12) bytes 1 TiB = 2**40 bytes 2*(10**12)/(2**40) = 1.8189894 TiB = 1.82 TiB (your computer may show this size number) 26. What are the largest and smallest integers (in decimal) an 8-bit word can hold using a sign-magnitude representation? 8 bits can hold 2**8 (256) different numbers. The top bit is the sign bit, leaving 7 bits for the magnitude. (Half the of the 2**8 bit patterns are negative; half are positive.) 2**7 is 128, so we can have 128 negative numbers and 128 positive numbers. We start counting from zero, therefore: + (2**7 - 1) = +127 (128 numbers from +0 -> +127) - (2**7 - 1) = -127 (128 numbers from -0 -> -127) We have both plus zero and minus zero using sign/magnitude. 27. What are the largest and smallest integers (in decimal) an 8-bit word can hold using a one's complement representation? 8 bits can hold 2**8 (256) different numbers. The top bit is the sign bit, so half the bit patterns are negative. (Half the of the 2**8 bit patterns are negative; half are positive.) 2**8 divided by two is 2**7 = 128, so we can have 128 negative numbers and 128 positive numbers. We start counting from zero, therefore: + (2**7 - 1) = +127 (128 numbers from +0 -> +127) - (2**7 - 1) = -127 (128 numbers from -0 -> -127) We have both plus zero and minus zero using one's complement. 28. What are the largest and smallest integers (in decimal) an 8-bit word can hold using a two's complement representation? 8 bits can hold 2**8 (256) different numbers. The top bit is the sign bit, so half the bit patterns are negative. (Half the of the 2**8 bit patterns are negative; half are positive.) 2**8 divided by two is 2**7 = 128, so we can have 128 negative numbers and 128 positive numbers. We start counting from zero, but due to the "flip bits and add one", there is no "minus zero". + (2**7 - 1) = +127 (128 numbers from +0 -> +127) - (2**7) = -128 (128 numbers from -1 -> -128 -- we start at -1 not -0) We have only one zero using two's complement. 29. What are the largest and smallest integers a 16-bit word can hold using a sign-magnitude representation? 16 bits can hold 2**16 (65,536) different numbers. The top bit is the sign bit, leaving 15 bits for the magnitude. (Half the of the 2**16 bit patterns are negative; half are positive.) 2**15 is 32,768, so we can have 32,768 negative numbers and 32,768 positive numbers. We start counting from zero, therefore: + (2**15 - 1) = +32,767 (32,768 numbers from +0 -> +32,767) - (2**15 - 1) = -32,767 (32,768 numbers from -0 -> -32,767) We have both plus zero and minus zero using sign/magnitude. 30. What are the largest and smallest integers a 16-bit word can hold using a one's complement representation? The top bit is the sign bit, so half the bit patterns are negative. (Half the of the 2**16 bit patterns are negative; half are positive.) 2**16 divided by two is 2**15 = 32,768, so we can have 32,768 negative numbers and 32,768 positive numbers. We start counting from zero, so: + (2**15 - 1) = +32,767 (32,768 numbers from +0 -> +32,767) - (2**15 - 1) = -32,767 (32,768 numbers from -0 -> -32,767) We have both plus zero and minus zero using one's complement. 31. What are the largest and smallest integers a 16-bit word can hold using a two's complement representation? 16 bits can hold 2**16 (65,536) different numbers. The top bit is the sign bit, so half the bit patterns are negative. (Half the of the 2**16 bit patterns are negative; half are positive.) 2**16 divided by two is 2**15 = 32,768, so we can have 32,768 negative numbers and 32,768 positive numbers. We start counting from zero, but due to the "flip bits and add one", there is no "minus zero". + (2**15 - 1) = +32,767 (32,768 numbers from +0 -> +32,767) - (2**15) = -32,768 (32,768 numbers from -1 -> -32,768 -- start at -1) We have only one zero using two's complement. 32. Generalize: For an N-bit word size, express as a formula using N as a power of two (i.e. using 2**N) what are the largest (most positive) and smallest (least positive) integers possible for: a) N-bit unsigned b) N-bit one's complement c) N-bit signed-magnitude d) N-bit two's complement Your formulas should produce the answers you gave in the above questions, e.g. your formula should output "+1023" for N=10 unsigned. a) N-bit unsigned: Largest = (2**N) - 1 Smallest = 0 b) N-bit one's complement: Largest = + ( (2**(N-1)) - 1 ) Smallest = - ( (2**(N-1)) - 1 ) c) N-bit signed-magnitude: Largest = + ( (2**(N-1)) - 1 ) Smallest = - ( (2**(N-1)) - 1 ) d) N-bit two's complement: Largest = + ( (2**(N-1)) - 1 ) Smallest = - ( (2**(N-1)) ) 33. What is the minimum number of binary bits needed to represent 187 items? Knowing your powers-of-two table makes this a quick answer. 2**7 = 128 items - TOO SMALL 2**8 = 256 items - BIG ENOUGH Therefore we need 8 bits which can hold 0 to 255 (unsigned) 34. What is the minimum number of binary bits needed to represent 31,386 items? Knowing your powers-of-two table makes this a quick answer. 2**14 = 16,384 items (a number to remember) - TOO SMALL 2**15 = 32,768 items (a number to remember) - BIG ENOUGH Therefore we need 15 bits which can hold 0 to 32,767 (unsigned) 35. What is the minimum number of binary bits needed to represent the number of days in a week? Need to represent seven items: 1 through 7 or 0 through 6. 2**2 = 4 items - TOO SMALL 2**3 = 8 items - BIG ENOUGH Seven items can be counted with a minimum of three bits. (Three bits can count 2**3 things.) 36. What is the minimum number of binary bits needed to represent the number of each day in the year, if the number of days in the year can be used positive or negative (e.g. "minus 300 days" or "today - 300")? Knowing your powers-of-two table makes this a quick answer. If we only needed to count positive year days, from 0 to 366, that is only 367 different numbers and we could use only 9 bits, because 2**9 can count 512 different things. Since we need to represent -366 through +366, we need to represent 366+367=733 different numbers, which needs at least 10 bits. Using two's complement (and the formula above), we choose 10 bits with range: -(2**9) to +((2**9)-1) or -512 to +511 37. Develop a binary encoding scheme which could be used to encode a field to represent one of the weeks of the year. Use the minimum number of bits. Knowing your powers-of-two table makes this a quick answer. 52 weeks in a year. 2**5 = 32 - TOO SMALL 2**6 = 64 - BIG ENOUGH Therefore we need 6 bits which can hold 0 to 63 (unsigned) 38. How many different numbers can be represented in 15 bits? The formula (from above) is 2**N. 2**15 = 32,768 different numbers (a number to remember) 39. What is the largest unsigned positive number that can be represented in 15 bits? For unsigned numbers, the formula (from above) is zero to (2**N)-1. 2**15 - 1 = 32,767 (because zero is one of the numbers) 40. What is the largest unsigned positive number that can be represented in one nybble? One nybble = half a byte = 4 bits 4 bits can count 2**4 = 16 things. For unsigned numbers, the formula (from above) is zero to (2**N)-1. Therefore the range is 0 to 15 Answer: 2**4 - 1 = 15 41. Unix/Linux has traditionally used a 32-bit signed integer to store the number of seconds since midnight on January 1, 1970, UTC. Calculate roughly in what year/month/day this value overflows and time would start going negative. (Modern Unix systems use 64 bit time.) 32 bits as a signed value can hold up to +((2**(32-1))-1) = (2**31)-1 = 2,147,483,647 seconds (positive). A year is about 365.25 days or 31,557,600 seconds. 2,147,483,647 / 31,557,600 = 68.049650385 years. Year 1970 + 68 years = year 2038 The remainder 0.049650385 years is about 18.134803121 days. January 1 + 18 days = January 19 (2038) A Wikipedia search confirms the actual date as 03:14:07 UTC on Tuesday, 19 January 2038: http://en.wikipedia.org/wiki/Year_2038_problem 42. Convert the following binary to hexadecimal. Hint: Your answer will have eight hex digits, all different: 1011000010010110010111101110110(2) = 0101 1000 0100 1011 0010 1111 0111 0110 (group binary from right) 5 8 4 B 2 F 7 6 (hex) = 584B2F76(16) 43. Express floating-point 123.654 as a normalized decimal number using scientific notation with four significant digits of precision. Normalized: 1.23654 x 10**2 Four digits: 1.236 x 10**2 (or 1.237 with rounding) In program code (Java) write this as 1.236e2 (1.236 times 10**2) 44. Add floating-point decimal 1243000.0 to 1.6 and express the result as a normalized decimal number using scientific notation with four significant digits of precision. Decimal addition: 1243000.0 + 1.6 = 1243001.6 decimal Normalized: 1.2430016 x 10**6 Four digits: 1.243 x 10**6 Note that adding 1.6 had no effect, given the precision available. The smallest change you could make to the four-digit mantissa, e.g. change 1.243 to 1.244, changes the value of the number by 0.001 x 10**6 or 10**3. The exponent multiplies the change by 10**3. A one-digit change in the mantissa affects the value by a thousand! 45. Add *binary* floating-point 1101000.0 to 1.11 and express the result as a normalized binary number using (binary) scientific notation with four (binary) significant digits of precision. Binary addition: 1101000.0 + 1.11 = 1101001.11 binary Normalized: 1.10100111 x 2**6 Four digits: 1.101 x 2**6 Note that adding 1.11 had no effect, given the precision available. The smallest change you could make to the four-bit mantissa, e.g. change 1.101 to 1.100, changes the value of the number by 0.001 x 2**6 or 2**3. The exponent multiplies the change by 2**3. A one-bit change in the mantissa affects the value by eight! 46. Looking at the two previous questions, is it possible in a computer to add a small floating-point number to a larger floating-point number without having any effect, i.e. is it true that A+B=A for certain floating-point values where B is much smaller than A? Class Notes Reference: 090_FloatingPoint.htm Yes. Both previous questions show cases where A+B=A when A is big and B is small. Because the number of bits of precision is fixed in ordinary floating-point arithmetic inside a computer, there will be some arithmetic that will not have enough precision to represent the true answer. Adding two values of greatly differing magnitudes (e.g. add 3 to 10**99) usually leaves the larger number unchanged, because there are not enough bits of precision to represent the small number being added to it. See the FunnyMath0.java program. 47. Assuming unsigned binary encoding, what decimal value is represented by the binary pattern: 1 0 1 0 1 0 0 1 ? 128 64 32 16 8 4 2 1 <-- powers of two --- -- -- -- - - - - 1 0 1 0 1 0 0 1 = 10101001(2) in binary = 1*128 + 0*64 + 1*32 + 0*16 + 1*8 + 0*4 + 0*2 + 1*1 = 169(10) decimal 48. Conversions from different bases and representations to decimal: a) Given the digits 101011(16), convert to decimal from base "16" = b) Given the digits 101011(10), convert to decimal from base "10" = c) Given the digits 101011(8), convert to decimal from base "8" = d) Given the digits 101011(2), convert to decimal from base "2" = e) Given the digits 101011(-2), convert to decimal from base "-2" = f) Given the digits 101011(2), convert to decimal from bias-127 = g) Given the digits 101011(2), convert to decimal from bias-63 = h) Given the digits 101011(2), convert to decimal from bias-31 = i) Given the digits 101011(2), convert to decimal from bias-16 = Reference: http://en.wikipedia.org/wiki/Signed_number_representations Class Notes Reference: 060_different_binary_integers.html All of these just multiply out and add up using powers of the given base. I'll do one example in full to show the method (the strange base -2); generalize the same method to the other bases. a) 101011(16) = 1048576 + 4096 + 16 + 1 = 1052689 decimal b) 101011(10) = 100000 + 1000 + 10 + 1 = 101011 decimal (identity!) c) 101011(8) = 32768 + 512 + 8 + 1 = 33289 decimal d) 101011(2) = 32 + 8 + 2 + 1 = 43 decimal e) Given the digits 101011(-2), convert to decimal from base "-2" = Successive powers of a negative base alternate in sign! Powers: -2^5 -2^4 -2^3 -2^2 -2^1 -2^0 Values: -32 16 -8 4 -2 1 Digits: 1 0 1 0 1 1 --------------------------------- Add Up: -32 + 0 + -8 + 0 + -2 + 1 = -41 base 10 For all the bias (or "excess" notation) numbers, we first convert the binary pattern to unsigned decimal, i.e.: 101011(2) = 43 decimal then we subtract the given bias to get the actual value: f) 101011(2), bias-127 = 43-127 = -84 decimal (same as IEEE 754 exponent) g) 101011(2), bias-63 = 43- 63 = -20 h) 101011(2), bias-31 = 43- 31 = 12 i) 101011(2), bias-16 = 43- 16 = 27 IEEE 754 Single Precision Floating-Point uses an excess-127 representation for its 8-bit exponent field. 49. In a 16-bit word, unsigned, what is the decimal value of the top bit? (What is the decimal value of an unsigned binary 16-bit number that has only the highest bit set?) The "top" bit is the leftmost, most significant bit. Bit 0 (on the right) is 2**0 so bit 15 (on the left) is 2**15 which is 32,768 (a famous number in computer science - remember it). 50. True/False: The most negative two's complement number has only the sign bit turned on and all the other bits are zeroes. True. Adding one to the most positive bit pattern gives the most negative bit pattern, e.g. in 6 bits: 011111+1=100000 = -64 decimal in 10 bits: 0111111111+1=1000000000 = -1024 decimal 51. True/False: Two's complement -1 is always "all bits on". True, no matter how many bits you use. -1 = 11111111(2) in eight bits. -1 = 1111(2) in four bits. If you add one to it, you get zero - all bits off. Subtracting one from zero always gives "all bits on". 52. What happens mathematically to the range of values possible in a word if you increase the word length by one bit, e.g. from eight bits to nine bits or from 100 bits to 101 bits? The range of possible values doubles. For example, 10 bits holds 2**10 values (1024 values) and 11 bits holds 2**11 values (2048 values). -- | Ian! D. Allen - idallen@idallen.ca - Ottawa, Ontario, Canada | Home Page: http://idallen.com/ Contact Improv: http://contactimprov.ca/ | College professor (Free/Libre GNU+Linux) at: http://teaching.idallen.com/ | Defend digital freedom: http://eff.org/ and have fun: http://fools.ca/