Fundamental of CS

Homework3 Topic: Integer Representation (Two’s complement) • • • • Integers are heavily used in real world applications. Since sign (+ or -) is also binary, one of the bits can be used to represent the sign. Sign-magnitude representation is easy for us to understand, but hard to implement in computers. Disadvantages includes, o Two zeroes o To add, first check the sign  If the signs are same, • keep the sign and just add the magnitude, check overflow  if the signs are different • compare the magnitudes o keep the sign of the largest o subtract the smallest magnitude from the largest o To subtract, x – y = x + (-y); y to -y is easy; just invert the first bit Almost all contemporary computers use two’s compliment representation.. Compare (positional number systems representation) • What is 1011 represent in Unsigned: Two’s complement: Sign-magnitude: • 1 * 2^3 + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = 8 + 0 + 2 + 1 = 11 (-1) * 2^3 + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = -8 + 0 + 2 + 1= -5 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = 0 + 2 + 1= -3 What is 0011 represent in Unsigned: Two’s complement: Sign-magnitude: 0 * 2^3 0 * 2^3 If the first digit is 0, all are same + + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = 0 + 0 + 2 + 1 = 3 + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = 0 + 0 + 2 + 1= 3 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = + 0 + 2 + 1= 3 For simplicity, first, we consider 4-bit representations first: HELP: For help on arithmetic operations, check the last two pages. For 4-bit size, how many pattern are possible? 2^4 = 16 (see far left patterns in the table below) 1. Which numbers are represented by each of these patterns in two’s complement representation? Fill-in the rest. 4-bit patterns 0000 0001 0101 Unsigned Integer 0 1 0111 1000 1001 7 8 1011 11 1111 15 Integer Sign-Magnitude Rep. Two’s Compliment Rep. 0 +0 1 +1 +7 7 -7 2. What is the range in 4-bit two’s complement representation? 3. How are the following numbers represented in 4-bit two’s complement representation? 0 , 1, -1, 5, 6, -6, 8 4. What numbers the following patterns represent in 4-bit two’s complement representation? 0000, 0001, 1111, 0101, 1011,, 0111, 1001, 1000 5. Perform the indicated operations in 4-bit two’s complement representation. State if there is an overflow a. 1111 + 0001 A digit-overflow at the MSB is an overflow- is it true? yes/no b. 1111 – 0001 A digit-overflow at the MSB is an overflow- is it true? c. 0000 – 0001 If there is no digit-overflow at the MSB, overflow is not possible- is it true? yes/no d. 1010 + 0011 If there is no digit-overflow at the MSB, overflow is not possibleis it true? always true/sometimes true/never true e. 1111 – 0001 f. 1010 – 1011 6. How overflow can be detected when adding two numbers in 4-bit two’s complement representation? A. If you add two different sign numbers, overflow will _____ B. If you add two same sign numbers, overflow will occur if _____ x – y = x + (-y) C. If you subtract two different sign numbers, overflow will occur if (see B ?) D. If you subtract two same sign numbers, overflow will (see A ?) E. A digit-overflow at the MSB is an overflow- is it true? always/sometimes/never F. If there is no digit-overflow at the MSB, overflow is not possible- is it true? always/ sometimes/ never Now, consider 8-bit two’s complement representation: 7. For 8-bit size, how many patterns are possible? 8. Which numbers are represented by each of these patterns in different types of representation? Fillin the rest. 8-bit patterns 0000000 0000001 0 1 Integer Two’s Compliment 0 1 127 128 -128 Unsigned Integer Sign-Magnitude 00001111 01111101 01111111 10000000 10000001 10001111 111111111 255 9. What is the range for 8-bit in two’s complement representation? 10. How are the following numbers represented in 8-bit two’s complement representation? 0 , 1, -1, 10, 50, -50, 126, -126, 130 11. What numbers the following patterns represent in 8-bit two’s complement representation? 00000000, 00010000, 11111111, 01011010, 10000001, 10101010 12. Perform the indicated operations in 8-bit two’s complement representation. State if there is an overflow a. 11111111 + 11111110 A digit-overflow at the MSB is an overflow- is it true? yes/no b. 10000001 + 1000000 A digit-overflow at the MSB is an overflow- is it true? always true/sometimes true/never true c. 00000011 + 00000001 If there is no digit-overflow at the MSB, overflow is not possible – is it true? yes/no d. 01111111 + 00000001 If there is no digit-overflow at the MSB, overflow is not possibleis it true? always true/sometimes true/never true e. 11111111 – 00000001 f. 10101010 – 10000011 13. Suppose the bit patterns in 8-bit two’s complement representation are replaced by hexadecimal digits. Perform the indicated operations. a. A1 + 2A b. A1 + 81 c. A1 – 9A d. FF – AA Java: byte a = 127, b = -128 // or a = 0x7F, b =? System.out.println(++a, + “ “ + –b); int p = Integer.MAX_VALUE, q = Integer.MAX_VALUE System.out.println(p + “ “ + q); System.out.println(++p + “ “ + –q); What will be printed? HELP: All examples, consider 4-bit representation. Unsigned Integer (magnitude) To add two numbers. Both numbers will always have SAME SIGNnegative numbers are not available. There is no sign bit Just add their magnitude e.g. 3 + 12 = 0011 + 1100 = 1111 = 15 If there is a carry bit out of MSB bits, OVERFLOW. 3 + 13 = 0011 + 1101 = (1) 0000 :overflow The range is 0 – 15, 16 is overflow Sign-Magnitude To add two numbers 1) If both have same sign: Keep the same sign for the result. Just add their magnitudes e.g.: 3 + 1 = 0011 + 0001 = 0|011+ 001 = 0|100 = 0100 = 4 e.g. -3 + -1 1011 + 1001 = 1|011 + 001 = 1|100 = 1100 = -4 Integer Two’s compliment To add two numbers: Regardless of same sign or different signs, just add the numbers and discard the carry bit, if any, from the MSB bits. After adding, if there is a carry bit out of MSB bits of magnitudes, OVERFLOW e.g: 7 + 1 0111 + 0001 = 0|(111+001) = 0| (1) 000 : overflow e.g -7 + -1 = 1111 + 1001 = 1|(111+001) = 1| (1) 000 : overflow 2) If signs are different: OVERFLOW NOT POSSIBLE a) Compare the magnitude of the numbers, if the subtrahend is smaller, the sign of the result is positive, Subtract the magnitude of the smaller number from the largest, and keep the result as the magnitude of the result. e.g. 1 + -6 OR -6 + 1 0001 + 1110 ; signs are different, the sign of the number with the largest magnitude is negative, therefore the sign of the result is negative (1). Keep this as the sign of the final result. Compare to 001, the largest magnitude is 110,; therefore, subtract 001 from 110 and keep the result as the magnitude of the final result. Even if there is a carry out of MSB bits, it may not be an overflow: e.g. -1 + -1 (add small negative numbers) 1111 + 1111 = (1) 1110 = 1110 = -2 There may be an overflow, even there is no carry out of MSB bits. e.g. 5 + 3 (add big positive numbers) 0101 + 0011 = 1000 = -8 (overflow) OVERFLOW is detected by checking the sign. If the signs of the numbers are different, overflow NOT possible. If the signs are same, and the sign of the result is different, it is an Overflow. e.g.: 3 + 1 = 0011 + 0001 = 0100 = 4 e.g. 3 + -1 1101 + 1111 = (1|1100 = 1100 = -4 e.g: 7 + 1 0111 + 0001 = 1000 = -8 : overflow e.g. -7 + -1 = 1001 + 1111 = (1)1000 = 1000 = -8 0001 + 1110 = 1 | (110 – 001) = 1 | 101 = 1101 = -5 e.g. 6 + -1 OR -1 + 6 1001 + 0110 ; signs are different, the sign of the number with the largest magnitude is positive, therefore the sign of the result is positive (0). Keep this as the sign of the final result. Compare to 001, the largest magnitude is 110,; therefore, subtract 001 from 110 and keep the result as the magnitude of the final result. 1001 + 0110 = 0 | (110 – 001) = 0 | 101 = 0101 = 5 To subtract two numbers (both will be positive 1) Compare the numbers, If subtrahend is smaller than the other number, just subtract 2) If subtrahend is larger, OVERFLOW Negate: not possible To subtract two numbers 1) Convert the sign of the subtrahend (negate the subtrahend- just invert MSB) 2) Now ADD (same as above) To subtract two numbers 1) Convert the sign of the subtrahend (negate the subtrahend- invert every bit of the number and add 1) 2) Now ADD (same as above) e.g. 5 – 2 = 5 + -2 0101 – 0010 = 0101 + 1010 = 0| (101 – 010) = 0 | 011 = 0011 = 3 e.g. -5 – 2 = -5 + -2 1101 – 0010 = 1101 + 1010 = 1|(101+010)= 1|111=1111= -7 e.g. -5 – 3 will be overflow- check e.g. 5 – -2 = 5 + 2 0101 – 1010 = 0101 + 0010 = =7 e.g. 5 – -3 will be overflow- check -5 – -2 = -5 + 2 1101 – 1010 = 1101 + 0101 = = -3 e.g. 5 – 2 = 5 + -2 0101 – 0010 = 0101 + 1110 = (1) 0011 = 0011 = 3 0| (101 – 010) = 0 | 011 = 0011 = 3 e.g.: -5 – 2 = -5 + -2 1011 + 1110 = (1)1001 = 1001 = -7 e.g. -5 – 4 will be overflow- check e.g 5 – -2 = 5 + 2 0101 + 0010 = 0111= 7 e.g 5 – -3 will be overflow-check e.g. -5 – -2 = -5 + 2 1011 + 0010 = 1101 = -3 Negate: Just invert the MSB Negate: invert all bits + 1

Collepals.com Plagiarism Free Papers

Are you looking for custom essay writing service or even dissertation writing services? Just request for our write my paper service, and we'll match you with the best essay writer in your subject! With an exceptional team of professional academic experts in a wide range of subjects, we can guarantee you an unrivaled quality of custom-written papers.

Get ZERO PLAGIARISM, HUMAN WRITTEN ESSAYS

Why Hire Collepals.com writers to do your paper?

Quality- We are experienced and have access to ample research materials.

We write plagiarism Free Content

Confidential- We never share or sell your personal information to third parties.

Support-Chat with us today! We are always waiting to answer all your questions.