Question

Complete the following table indicating whether or not signed overflow occurs for the given N-bit arithmetic operations. As an example, the first row is done for you and explained below the table. Show your work! Operation Number of bits Signed overflow?

operation	Number of bits	Signed Overflow?
23+10	6	Yes
16+15	6
-123-134	9
16338521 - 225183	40

TIPS: In 6 bits, the range of signed numbers is [-2 N-1 , 2N-1 – 1], or [-32, 31]. The sum 23 + 10 gives the answer 33, which is outside the range, hence signed overflow occurs.

Answer 1

Answer:
---------
23+10 -> Yes
16+15   ->  No
-123-134    ->  Yes
16338521 - 225183   ->  No

Explanation:
----------------
a)
Number: 23
Let's convert this to two's complement binary
Since this is a positive number. we can directly convert this into binary
Divide 23 successively by 2 until the quotient is 0
23/2 = 11, remainder is 1
11/2 = 5, remainder is 1
5/2 = 2, remainder is 1
2/2 = 1, remainder is 0
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 10111
Adding 1 zeros on left hand side of this number to make this of length 6
so, 23 in 2's complement binary is 010111

Number: 10
Let's convert this to two's complement binary
Since this is a positive number. we can directly convert this into binary
Divide 10 successively by 2 until the quotient is 0
10/2 = 5, remainder is 0
5/2 = 2, remainder is 1
2/2 = 1, remainder is 0
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 1010
Adding 2 zeros on left hand side of this number to make this of length 6
so, 10 in 2's complement binary is 001010

Adding 010111 and 001010 in binary
    010111
    001010
-----------
 (0)100001
-----------
Sum does not produces a carry
So, sum of these numbers in binary is 100001

Verification:
---------------
sum = 100001
since left most bit is 1, this number is negative number.
so, follow these steps below to convert this into a decimal value.
I. first flip all the bits. Flip all 0's to 1 and all 1's to 0.
   100001 is flipped to 011110
II. Add 1 to above result
011110 + 1 = 011111
III. Now convert this result to decimal value
=> 11111
=> 1x2^4+1x2^3+1x2^2+1x2^1+1x2^0
=> 1x16+1x8+1x4+1x2+1x1
=> 16+8+4+2+1
=> 31
Answer: -31
23+10 must be 33
This is not correct since we can verify that 23+10 not equals -31
so, Signed Overflow is Yes

b)
Number: 16
Let's convert this to two's complement binary
Since this is a positive number. we can directly convert this into binary
Divide 16 successively by 2 until the quotient is 0
16/2 = 8, remainder is 0
8/2 = 4, remainder is 0
4/2 = 2, remainder is 0
2/2 = 1, remainder is 0
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 10000
Adding 1 zeros on left hand side of this number to make this of length 6
so, 16 in 2's complement binary is 010000

Number: 15
Let's convert this to two's complement binary
Since this is a positive number. we can directly convert this into binary
Divide 15 successively by 2 until the quotient is 0
15/2 = 7, remainder is 1
7/2 = 3, remainder is 1
3/2 = 1, remainder is 1
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 1111
Adding 2 zeros on left hand side of this number to make this of length 6
so, 15 in 2's complement binary is 001111

Adding 010000 and 001111 in binary
    010000
    001111
-----------
 (0)011111
-----------
Sum does not produces a carry
So, sum of these numbers in binary is 011111

Verification:
---------------
sum = 011111
since left most bit is 0, this number is positive
so, we can directly convert this into a decimal value
=> 11111
=> 1x2^4+1x2^3+1x2^2+1x2^1+1x2^0
=> 1x16+1x8+1x4+1x2+1x1
=> 16+8+4+2+1
=> 31
Answer: 31
This is correct since we can verify that 16+15 = 31
so, Signed Overflow is No

c)
Number: -123
Let's convert this to two's complement binary
This is negative. so, follow these steps to convert this into a 2's complement binary
Step 1:
Divide 123 successively by 2 until the quotient is 0
123/2 = 61, remainder is 1
61/2 = 30, remainder is 1
30/2 = 15, remainder is 0
15/2 = 7, remainder is 1
7/2 = 3, remainder is 1
3/2 = 1, remainder is 1
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 1111011
Adding 2 zeros on left hand side of this number to make this of length 9
So, 123 in normal binary is 001111011
Step 2: flip all the bits. Flip all 0's to 1 and all 1's to 0.
   001111011 is flipped to 110000100
Step 3:. Add 1 to above result
110000100 + 1 = 110000101
so, -123 in 2's complement binary is 110000101

Number: -134
Let's convert this to two's complement binary
This is negative. so, follow these steps to convert this into a 2's complement binary
Step 1:
Divide 134 successively by 2 until the quotient is 0
134/2 = 67, remainder is 0
67/2 = 33, remainder is 1
33/2 = 16, remainder is 1
16/2 = 8, remainder is 0
8/2 = 4, remainder is 0
4/2 = 2, remainder is 0
2/2 = 1, remainder is 0
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 10000110
Adding 1 zeros on left hand side of this number to make this of length 9
So, 134 in normal binary is 010000110
Step 2: flip all the bits. Flip all 0's to 1 and all 1's to 0.
   010000110 is flipped to 101111001
Step 3:. Add 1 to above result
101111001 + 1 = 101111010
so, -134 in 2's complement binary is 101111010

Adding 110000101 and 101111010 in binary
    110000101
    101111010
--------------
 (1)011111111
--------------
Sum produces a carry of 1. We can ignore that carry.
So, sum of these numbers in binary is 011111111

Verification:
---------------
sum = 011111111
since left most bit is 0, this number is positive
so, we can directly convert this into a decimal value
=> 11111111
=> 1x2^7+1x2^6+1x2^5+1x2^4+1x2^3+1x2^2+1x2^1+1x2^0
=> 1x128+1x64+1x32+1x16+1x8+1x4+1x2+1x1
=> 128+64+32+16+8+4+2+1
=> 255
Answer: 255
-123+-134 must be -257
This is not correct since we can verify that -123+-134 not equals 255
so, Signed Overflow is Yes

d)
Number: 16338521
Let's convert this to two's complement binary
Since this is a positive number. we can directly convert this into binary
Divide 16338521 successively by 2 until the quotient is 0
16338521/2 = 8169260, remainder is 1
8169260/2 = 4084630, remainder is 0
4084630/2 = 2042315, remainder is 0
2042315/2 = 1021157, remainder is 1
1021157/2 = 510578, remainder is 1
510578/2 = 255289, remainder is 0
255289/2 = 127644, remainder is 1
127644/2 = 63822, remainder is 0
63822/2 = 31911, remainder is 0
31911/2 = 15955, remainder is 1
15955/2 = 7977, remainder is 1
7977/2 = 3988, remainder is 1
3988/2 = 1994, remainder is 0
1994/2 = 997, remainder is 0
997/2 = 498, remainder is 1
498/2 = 249, remainder is 0
249/2 = 124, remainder is 1
124/2 = 62, remainder is 0
62/2 = 31, remainder is 0
31/2 = 15, remainder is 1
15/2 = 7, remainder is 1
7/2 = 3, remainder is 1
3/2 = 1, remainder is 1
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 111110010100111001011001
Adding 16 zeros on left hand side of this number to make this of length 40
so, 16338521 in 2's complement binary is 0000000000000000111110010100111001011001

Number: -225183
Let's convert this to two's complement binary
This is negative. so, follow these steps to convert this into a 2's complement binary
Step 1:
Divide 225183 successively by 2 until the quotient is 0
225183/2 = 112591, remainder is 1
112591/2 = 56295, remainder is 1
56295/2 = 28147, remainder is 1
28147/2 = 14073, remainder is 1
14073/2 = 7036, remainder is 1
7036/2 = 3518, remainder is 0
3518/2 = 1759, remainder is 0
1759/2 = 879, remainder is 1
879/2 = 439, remainder is 1
439/2 = 219, remainder is 1
219/2 = 109, remainder is 1
109/2 = 54, remainder is 1
54/2 = 27, remainder is 0
27/2 = 13, remainder is 1
13/2 = 6, remainder is 1
6/2 = 3, remainder is 0
3/2 = 1, remainder is 1
1/2 = 0, remainder is 1
Read remainders from the bottom to top as 110110111110011111
Adding 22 zeros on left hand side of this number to make this of length 40
So, 225183 in normal binary is 0000000000000000000000110110111110011111
Step 2: flip all the bits. Flip all 0's to 1 and all 1's to 0.
   0000000000000000000000110110111110011111 is flipped to 1111111111111111111111001001000001100000
Step 3:. Add 1 to above result
1111111111111111111111001001000001100000 + 1 = 1111111111111111111111001001000001100001
so, -225183 in 2's complement binary is 1111111111111111111111001001000001100001

Adding 0000000000000000111110010100111001011001 and 1111111111111111111111001001000001100001 in binary
    0000000000000000111110010100111001011001
    1111111111111111111111001001000001100001
---------------------------------------------
 (1)0000000000000000111101011101111010111010
---------------------------------------------
Sum produces a carry of 1. We can ignore that carry.
So, sum of these numbers in binary is 0000000000000000111101011101111010111010

Verification:
---------------
sum = 0000000000000000111101011101111010111010
since left most bit is 0, this number is positive
so, we can directly convert this into a decimal value
=> 111101011101111010111010
=> 1x2^23+1x2^22+1x2^21+1x2^20+0x2^19+1x2^18+0x2^17+1x2^16+1x2^15+1x2^14+0x2^13+1x2^12+1x2^11+1x2^10+1x2^9+0x2^8+1x2^7+0x2^6+1x2^5+1x2^4+1x2^3+0x2^2+1x2^1+0x2^0
=> 1x8388608+1x4194304+1x2097152+1x1048576+0x524288+1x262144+0x131072+1x65536+1x32768+1x16384+0x8192+1x4096+1x2048+1x1024+1x512+0x256+1x128+0x64+1x32+1x16+1x8+0x4+1x2+0x1
=> 8388608+4194304+2097152+1048576+0+262144+0+65536+32768+16384+0+4096+2048+1024+512+0+128+0+32+16+8+0+2+0
=> 16113338
Answer: 16113338
This is correct since we can verify that 16338521+-225183 = 16113338
so, Signed Overflow is No