2.7.PROBLEMS 19 6.A fistful of(binary)digits Your imaginary computer represents integers using 5 and only 5 bits!Fill in the blank spots in the following table.The signed integers follow the two's-complement rule discussed in class. Binary Hexadecimal Unsigned Int Signed Int 00000 00 0 0 00001 01 1 1 00010 02 2 2 00011 03 3 3 00100 04 4 4 00101 05 5 5 00110 06 6 00111 07 7 7 01000 08 8 01001 09 9 01010 0A 10 01011 0B 11 01100 OC 12 01101 OD 13 01110 0E 14 01111 OF 15 10000 10 16 10001 11 17 10010 12 10011 13 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 -3 11110 -2 11111 -1
2.7. PROBLEMS 19 6. A fistful of (binary) digits Your imaginary computer represents integers using 5 andonly 5 bits! Fill in the blank spots in the following table. The signedintegers follow the two’s-complement rule discussed in class. Binary Hexadecimal Unsigned Int Signed Int 00000 00 0 0 00001 01 1 1 00010 02 2 2 00011 03 3 3 00100 04 4 4 00101 05 5 5 00110 06 6 6 00111 07 7 7 01000 08 8 01001 09 9 01010 0A 10 01011 0B 11 01100 0C 12 01101 0D 13 01110 0E 14 01111 0F 15 10000 10 16 10001 11 17 10010 12 10011 13 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 -3 11110 -2 11111 -1
20 CHAPTER 2.DATA REPRESENTATIONS 7.These digits will give you the fidgets. Your imaginary computer still represents integers using 5 and only 5 bits!The result of an arithmetic operation with two integers always results in a 5-bit result.Higher-order bits are "lost'”. Do your calculations in binary arithmetic and SHOW YOUR WORK!Quote your results of your calculations in binary,signed integer (2s-complement scheme),unsigned and hexadecimal integer representations.You may use the table that you completed in the previous question. (a)What is the sum of the unsigned integers 3 and 4? (b)What is the sum of the unsigned integers 16 and 17? (c)What is the sum of the signed integers-2 and-3? (d)What is the sum of the signed integers-16 and-16? (e)What is the product of the unsigned integers 3 and 4? (f)What is the product of the signed integers-2 and-3? (g)What is the product of the signed integers-16 and-16?
20 CHAPTER 2. DATA REPRESENTATIONS 7. These digits will give you the fidgets. Your imaginary computer still represents integers using 5 andonly 5 bits! The result of an arithmetic operation with two integers always results in a 5-bit result. Higher-order bits are “lost”. Do your calculations in binary arithmetic and SHOW YOUR WORK! Quote your results of your calculations in binary, signedinteger (2s-complement scheme), unsigned andhexadecimal integer representations. You may use the table that you completed in the previous question. (a) What is the sum of the unsignedintegers 3 and4? (b) What is the sum of the unsignedintegers 16 and17? (c) What is the sum of the signedintegers -2 and-3? (d) What is the sum of the signedintegers -16 and-16? (e) What is the product of the unsignedintegers 3 and4? (f) What is the product of the signedintegers -2 and-3? (g) What is the product of the signedintegers -16 and-16?
2.7.PROBLEMS 21 8.Bits and bytes?Again! In the following table,the column 1 represents bit patterns on a 6-bit computer. (a)In the 2'nd column,write in the complement of the bit pattern in column 1 (b)In the 3'rd column,write in the two's complement of the bit pattern in column 1 (c)In the 4'th column,write in the two's complement of the bit pattern in column 3 (d)In the 5'th column,put a check mark if the bit pattern in column 1 represents a positive signed int. (e)In the 6'th column,put a check mark if the bit pattern in column 1 represents an odd unsigned int. (f)In the 7'th column,put a check mark if the bit pattern in column 1 represents an unsigned int that is divisible by 2. (g)In the 8'th column,put a check mark if the bit pattern in column 1 represents an unsigned int that is divisible by 4. (h)If the bit pattern in column 1 represents an odd unsigned int,write its unsigned int representation in column 9. Column 1 Column 2 Column 3 Column 4 Col 5 Col 6 Col 7 Col 8 Column 9 000010 111001 110110 000001 001101 110010 010010 110110 101111 101010
2.7. PROBLEMS 21 8. Bits and bytes? Again! In the following table, the column 1 represents bit patterns on a 6-bit computer. (a) In the 2’ndcolumn, write in the complement of the bit pattern in column 1 (b) In the 3’rdcolumn, write in the two’s complement of the bit pattern in column 1 (c) In the 4’th column, write in the two’s complement of the bit pattern in column 3 (d) In the 5’th column, put a check mark if the bit pattern in column 1 represents a positive signed int. (e) In the 6’th column, put a check mark if the bit pattern in column 1 represents an odd unsigned int. (f) In the 7’th column, put a check mark if the bit pattern in column 1 represents an unsigned int that is divisible by 2. (g) In the 8’th column, put a check mark if the bit pattern in column 1 represents an unsigned int that is divisible by 4. (h) If the bit pattern in column 1 represents an odd unsigned int, write its unsigned int representation in column 9. Column 1 Column 2 Column 3 Column 4 Col 5 Col 6 Col 7 Col 8 Column 9 000010 111001 110110 000001 001101 110010 010010 110110 101111 101010
22 CHAPTER 2.DATA REPRESENTATIONS 9.A bit challenging In the following table: 1)Convert the first 5 32-bit bit patterns to hex 2)indicate which bit patterns are divisible by 2(/2) 3)indicate which bit patterns are divisible by 4 (/4) 4)indicate which bit patterns represent positive or negative integers in two's-complement representation (+/-? 5)indicate which bit pattern represents the largest integer in two's-complement repre- sentation (>? 6)indicate which bit pattern represents the smallest integer in two's-complement rep- resentation,negative with the greatest magnitude(<?) 32-bit bit patterns hex /2?/4?-/+?>?<? 11110001001001101110010101000110 10000010000011001000001010111011 10110001100010110100111100000111 00100001110110010100110101111110 00101000101000010010101001010111 11101100100010000011010111101101 X 11110111000011000011101000101101 01100111010000000101100010110000 X 00111110000000111100011000001101 X 00001110110110011111101101011000 X 01101111000110100010111101101000 10101000000011101111101000100011 X 00000010001100100100110000010101 00111100101001111011101101110000 X 11000011010010110110101111110011 11010001101111101011101000000001 X 11010011111010110100010101001111 X 11110011000101111110111000110000 X 01001101111011100000001110111011 01111011101011110100001000100101 X 11011001110111111101110110101101 X 10001101101001010110101011110110 X 01000100011011110001001001110001 00111110101011001100011100100111 X 11101111011111001001010100011101 X 10011000101001011000001010111010 10111111100001000011010100110111 X 10011010000000111111101001101111 9A03FA6F
22 CHAPTER 2. DATA REPRESENTATIONS 9. A bit challenging In the following table: 1) Convert the first 5 32-bit bit patterns to hex 2) indicate which bit patterns are divisible by 2 (/2) 3) indicate which bit patterns are divisible by 4 (/4) 4) indicate which bit patterns represent positive or negative integers in two’s-complement representation (+/-?) 5) indicate which bit pattern represents the largest integer in two’s-complement representation (>?) 6) indicate which bit pattern represents the smallest integer in two’s-complement representation, negative with the greatest magnitude (<?) 32-bit bit patterns hex /2? /4? -/+? >? <? 1111 0001 0010 0110 1110 0101 0100 0110 1000 0010 0000 1100 1000 0010 1011 1011 1011 0001 1000 1011 0100 1111 0000 0111 0010 0001 1101 1001 0100 1101 0111 1110 0010 1000 1010 0001 0010 1010 0101 0111 1110 1100 1000 1000 0011 0101 1110 1101 X 1111 0111 0000 1100 0011 1010 0010 1101 X 0110 0111 0100 0000 0101 1000 1011 0000 X 0011 1110 0000 0011 1100 0110 0000 1101 X 0000 1110 1101 1001 1111 1011 0101 1000 X 0110 1111 0001 1010 0010 1111 0110 1000 X 1010 1000 0000 1110 1111 1010 0010 0011 X 0000 0010 0011 0010 0100 1100 0001 0101 X 0011 1100 1010 0111 1011 1011 0111 0000 X 1100 0011 0100 1011 0110 1011 1111 0011 X 1101 0001 1011 1110 1011 1010 0000 0001 X 1101 0011 1110 1011 0100 0101 0100 1111 X 1111 0011 0001 0111 1110 1110 0011 0000 X 0100 1101 1110 1110 0000 0011 1011 1011 X 0111 1011 1010 1111 0100 0010 0010 0101 X 1101 1001 1101 1111 1101 1101 1010 1101 X 1000 1101 1010 0101 0110 1010 1111 0110 X 0100 0100 0110 1111 0001 0010 0111 0001 X 0011 1110 1010 1100 1100 0111 0010 0111 X 1110 1111 0111 1100 1001 0101 0001 1101 X 1001 1000 1010 0101 1000 0010 1011 1010 X 1011 1111 1000 0100 0011 0101 0011 0111 X 1001 1010 0000 0011 1111 1010 0110 1111 9A03FA6F
Chapter 3 Algorithms and Pseudocodes In this chapter we introduce algorithms and ways with which algorithms can be represented. At the end of the chapter,we also talk a little about computer architecture,as a way of illustrating the operations that can happen inside a computer,when a part of an algorithm is executed. 3.1 What is an algorithm? An algorithm is a set of well-defined,unambiguous steps or instructions to be carried out in sequence to accomplish some task. An algorithm usually has a START point and a STOP point.Certainly any algorithm we shall encounter in this book will.The START may require some inputs and the STOP may provide some output. An algorithm is made of individual instructions. An instruction consists of a well-defined operation usually on some input (what the instruction receives)and usually producing output (what the instruction produces). Each instruction is well-defined and its outcome predictable if the instruction operates on valid input. There is a direction of logic flow or sequencing.Once an instruction is executed,it passes control to another instruction. There can only be a finite set of instructions. When executed(with valid input)an algorithm is guaranteed to terminate in a sensible way. 23
Chapter 3 Algorithms and Pseudocodes In this chapter we introduce algorithms and ways with which algorithms can be represented. At the endof the chapter, we also talk a little about computer architecture, as a way of illustrating the operations that can happen inside a computer, when a part of an algorithm is executed. 3.1 What is an algorithm? An algorithm is a set of well-defined, unambiguous steps or instructions to be carriedout in sequence to accomplish some task. • An algorithm usually has a START point anda STOP point. Certainly any algorithm we shall encounter in this book will. The START may require some inputs andthe STOP may provide some output. • An algorithm is made of individual instructions. • An instruction consists of a well-defined operation usually on some input (what the instruction receives) and usually producing output (what the instruction produces). • Each instruction is well-defined and its outcome predictable if the instruction operates on validinput. • There is a direction of logic flow or sequencing. Once an instruction is executed, it passes control to another instruction. • There can only be a finite set of instructions. • When executed(with validinput) an algorithm is guaranteedto terminate in a sensible way. 23