Computer Science Homework

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: 1 * 2^3 + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = 8 + 0 + 2 + 1 = 11 Two’s complement: (-1) * 2^3 + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = -8 + 0 + 2 + 1= -5 Sign-magnitude: - 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = - 0 + 2 + 1= -3 • What is 0011 represent in Unsigned: 0 * 2^3 + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = 0 + 0 + 2 + 1 = 3 Two’s complement: 0 * 2^3 + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = 0 + 0 + 2 + 1= 3 Sign-magnitude: + 0 * 2 ^2 + 1 * 2 ^1 + 1 * 2^0 = + 0 + 2 + 1= 3

If the first digit is 0, all are same

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 Unsigned Integer Integer Sign-Magnitude Rep. Two’s Compliment Rep.

0000 0 + 0 0

0001 1 + 1 1

0101

0111 7 +7 7

1000 8

1001

1011 11

1111 15 -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 possible- is 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? Fill- in the rest.

8-bit patterns

Unsigned Integer Integer Sign-Magnitude

Two’s Compliment

0000000 0 0

0000001 1 1

00001111

01111101

01111111 127

10000000 128 -128

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 possible- is 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)

Integer Sign-Magnitude Two’s compliment

To add two numbers. Both numbers will always have SAME SIGN- negative 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

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

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.

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. 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

To subtract two numbers 1) Convert the sign of the

subtrahend (negate the subtrahend- just invert MSB)

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

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 + 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: not possible

Negate: Just invert the MSB Negate: invert all bits + 1