Two's complement signed integers and overflow

What the representation promises

A bit pattern does not carry its own signedness. At width four, 1101 can mean unsigned 13 or two's-complement −3. This lesson uses fixed-width, two's-complement integers and an ideal adder that retains exactly n low bits. It does not assume a programming language permits signed wraparound. Before using a numerical rule, write the width, representation and requested result.

Prerequisites: unsigned place values, binary addition and basic Boolean gates. Goals: encode and decode signed values, extend their width without changing their value, and distinguish a signed overflow flag from an unsigned carry. Sign-magnitude, one's complement, multiplication, division and floating point require separate lessons.

For bits b_(n−1)…b_0, assign the top bit weight −2^(n−1), and every other bit its ordinary positive weight. Thus value = −b_(n−1)×2^(n−1) + Σ b_i×2^i for i=0…n−2. Equivalently, first read the pattern as unsigned U: if its top bit is 0, value=U; if its top bit is 1, value=U−2^n. The latter rule subtracts 2^n, not 2^(n−1).

Range and decoding

The least value is a 1 followed by zeros: −2^(n−1). The greatest is a 0 followed by ones: 2^(n−1)−1. There are still 2^n patterns, with one encoding of zero. The range is asymmetric because zero occupies one nonnegative pattern.

Four-bit pattern	Unsigned value U	Two's-complement value
0000	0	0
0111	7	7
1000	8	−8
1101	13	−3
1111	15	−1

Worked example 1: decode the 6-bit pattern 101101. Negative-weight method: −32+8+4+1=−19. Unsigned method: U=45 and 45−64=−19. The two independent checks agree. Treating the last five bits as a magnitude would give −13, which belongs to a different encoding convention.

Encoding and negation

To encode a negative value −m in n bits, first verify 1≤m≤2^(n−1), then write the unsigned value 2^n−m at that width. Another route is to invert every bit of the n-bit unsigned pattern for m and add 1, retaining n bits. The complement step produces 2^n−1−m; adding 1 yields 2^n−m. This explains the rule rather than merely memorizing it.

Worked example 2: encode −23 in eight bits. Start with 23=00010111; invert to 11101000; add 1 to get 11101001. Check U=233, and 233−256=−23. Starting at six bits would produce a different width but the same value if six-bit rules were used consistently. −23 fits in six bits because −32≤−23≤31.

There is one important boundary. Negating the most-negative n-bit value needs +2^(n−1), which is not representable at the same width. For four bits, invert 1000 to 0111 and add 1: the result is 1000 again. The bit operation completed, but it did not produce a representable +8. Widen first if an exact positive result is required. Negating zero gives zero after discarding the extra carry.

Sign extension is value preservation

To widen a two's-complement value, copy the original top bit into every new high position. For example, four-bit 1011 means −5; eight-bit 11111011 also means −5. Zero-extension to 00001011 instead gives +11. Positive values get leading zeros under both rules.

Why does sign extension work for a negative value? Adding one high 1 changes the negative weight from −2^(n−1) to −2^n and makes the old sign bit contribute +2^(n−1). Their total remains −2^(n−1). Repeat that argument for each added position. Removing high bits is not the inverse operation for arbitrary values: narrowing is value-preserving only when the value fits the new range.

Addition and signed overflow

Add the bit patterns normally and retain n bits. Interpret the retained pattern using the signed rule. The exact mathematical sum is representable only if it lies inside the n-bit signed range. Signed overflow in addition occurs exactly when the operands have the same sign and the retained result has the opposite sign. Different-sign addition cannot overflow: its result lies between the two input values.

Worked example 3: at width four, 0101+0100 = 1001. The exact signed sum is 5+4=9, outside −8…7. The retained pattern means −7, so signed overflow is 1. There is no carry beyond bit three, so carry-out is 0. This is a direct counterexample to “overflow means carry-out.”

Contrast 1110+1101 = 1 1011. Signed inputs are −2 and −3; the retained 1011 means −5, which is exact. Carry-out is 1 but signed overflow is 0. If the same inputs were unsigned, the sum would be 14+13=27 and unsigned overflow would occur. Flags answer different interpretation questions about the same hardware addition.

A second signed-overflow test is V = carry into the sign bit XOR carry out of the sign bit. The carries must come from the same n-bit addition, including any specified input carry. For ordinary two-operand addition with no initial carry, the sign test above is usually quicker.

Subtraction and a dependable routine

Compute a−b with a plus the bitwise complement of b plus 1, retaining n bits. Test the exact difference against the signed range, or use this subtraction sign rule: overflow occurs when a and b have different signs and the result's sign differs from a. Do not reuse the addition sign rule directly on a and b. Also do not assume the intermediate mathematical value −b fits when b is the most-negative value.

Worked example 4: four-bit 3−(−6) uses 0011 + complement(1010) + 1 = 0011+0101+0001 =1001. The mathematical difference is 9, so the result −7 indicates overflow. In contrast, −3−2 gives 1101+1101+0001 =1 1011; retained 1011 is −5 and fits. A subtraction carry's interpretation as borrow depends on the stated convention; this lesson uses exact signed range checking instead.

Key points and common mistakes

1. Decode first, compute the exact integer, check the range, then interpret retained bits.
2. Four-bit signed range is −8…7, not −7…7 and not −8…8.
3. The top bit has negative weight; it is not a detachable minus sign.
4. Sign extension copies the sign bit. Adding zeros to a negative pattern changes its value.
5. Carry-out alone does not detect signed overflow. Keep the exact sum and stored pattern distinct.
6. The most-negative value cannot be negated exactly at the same width. Hardware bit behavior is not a promise about C-language semantics.

Original practice

These six single-correct MCQs are original learning questions, not previous-year questions. Choose exactly one option.

C01. What is the value of the 6-bit two's-complement pattern 110101?

A. 53 B. −21 C. −11 D. −13

Answer: C

A is incorrect: 53 is the unsigned interpretation.

B is incorrect: −21 results from treating the low five bits as a magnitude.

C is correct: unsigned U=53 and 53−64=−11; also −32+16+4+1=−11.

D is incorrect: −13 has six-bit pattern 110011.

C02. Which 8-bit two's-complement pattern encodes −37?

A. 11011010 B. 11011011 C. 10100101 D. 00100101

Answer: B

A is incorrect: complementing 00100101 without adding 1 gives −38.

B is correct: 256−37=219, whose eight-bit pattern is 11011011.

C is incorrect: 10100101 means 165−256=−91, not −37.

D is incorrect: 00100101 represents positive 37.

C03. Extend the 5-bit two's-complement value 10110 to eight bits without changing its value.

A. 00010110 B. 10010110 C. 11110110 D. 11100110

Answer: C

A is incorrect: zero-extension changes −10 into +22.

B is incorrect: 10010110 represents −106, not −10.

C is correct: copy the sign bit 1 into all three new positions; 246−256=−10.

D is incorrect: 11100110 represents −26 because an original bit was changed.

C04. A 4-bit adder computes 0110+0011 with input carry 0. What are (retained pattern, carry-out, signed overflow)?

A. 1001, 1, 1 B. 1001, 0, 0 C. 1001, 0, 1 D. 0111, 0, 1

Answer: C

A is incorrect: unsigned 6+3=9 is below 16, so carry-out is 0.

B is incorrect: +9 exceeds the signed maximum +7, so signed overflow is 1.

C is correct: the low pattern is 1001, no fifth-bit carry occurs, and the signed sum is out of range.

D is incorrect: 0111 is 7; no saturation rule was specified.

C05. In 4-bit two's complement, which addition has carry-out 1 but no signed overflow?

A. 0101+0100 B. 1001+1010 C. 0111+0001 D. 1110+1101

Answer: D

A is incorrect: 5+4=9 has signed overflow and carry-out 0.

B is incorrect: −7+(−6)=−13 is below −8, so signed overflow occurs despite carry-out 1.

C is incorrect: 7+1=8 has signed overflow and carry-out 0.

D is correct: −2+(−3)=−5 fits; raw 14+13=27 gives low 1011 and carry-out 1.

C06. What happens when the 4-bit pattern 1000 is inverted and 1 is added, retaining four bits?

A. The pattern is 1000, but exact negation of −8 is not representable in four-bit two's complement. B. The pattern is 0000, because every number cancels itself. C. The pattern is 0111, representing +8. D. The pattern is 1000, representing +8 in four-bit two's complement.

Answer: A

A is correct: invert to 0111 then add 1 to obtain 1000; mathematical +8 is outside −8…7.

B is incorrect: negating a value is not adding it to itself.

C is incorrect: 0111 is the intermediate complement and represents +7.

D is incorrect: the retained pattern still decodes to −8, not +8.

Scope and sources

This is one bounded Digital Logic lesson, not complete GATE CS coverage. The official syllabus establishes relevance only; the derivations, examples and practice are original. Technical references were used to check representation and circuit conventions, not to reproduce their exercises.

• Official GATE 2027 CS syllabus Section 2
• MIT Computation Structures binary encoding
• Cornell two's-complement notes

Sources checked 14 October 2026.