4.3 Two's complement

Why this matters

A circuit that adds positive numbers is only half of arithmetic. If subtracting needed its own circuit, and negative numbers needed another, every design would carry three. Two's complement is the encoding that makes one adder serve all three: negation is a cheap bit trick, and subtraction becomes addition of a flipped number plus one. It is also the reading behind every signed comparison and every overflow in the next section.

Learning goals

State the range of $n$ -bit two's complement numbers, and the one value in it that has no negation.
Negate a number by inverting every bit and adding 1.
Subtract by adding the inverted second operand and a carry in of 1, and discard the final carry.
Read one bit pattern both as an unsigned and as a signed number.
Choose between sign extension and zero extension when widening a number before arithmetic.

Intuition first

Picture the dial of a combination lock with sixteen positions, numbered 0 to 15. Turn it one step back from 0 and you land on 15; turn it one step back from 15 and you land on 14. Going back by 3 and going forward by 13 end on the same position. So on this dial, "minus 3" and "plus 13" are the same move. An $n$ -bit adder is that dial with $2^n$ positions: it wraps around, and an addition that goes past the top returns to the bottom.

Two's complement reads the dial differently. The positions just below the wrap point are the negative numbers: one step back from 0000 is 1111, which is −1. The signed values jump somewhere else, halfway round the dial, between the largest positive number and the most negative one. The pattern that is $x$ steps forward from zero has a partner that is $x$ steps back, and an adder that already knows how to go forward by any amount can therefore go back. That is the whole idea.

The number wheel

Section 2.6 defined the signed reading (Definition 2.6.1): the leftmost bit has the weight $-2^{n-1}$ and the others keep their usual weights. The wheel below shows all sixteen 4-bit patterns with both readings.

Outer numbers are signed values, inner numbers are unsigned values. The red line is the jump from the largest positive value to the most negative one.

4-bit patterns
Bits	Unsigned	Signed
0000	0	0
0001	1	1
0010	2	2
0011	3	3
0100	4	4
0101	5	5
0110	6	6
0111	7	7
1000	8	-8
1001	9	-7
1010	10	-6
1011	11	-5
1100	12	-4
1101	13	-3
1110	14	-2
1111	15	-1

Figure 4.3.1. All sixteen 4-bit patterns, each with its unsigned and signed value. The signed values jump from the largest positive value to the most negative one.

Three facts follow from the weights. A pattern whose leftmost bit is 0 has the same value in both readings. Zero has one pattern and no other. And the range has one more negative value than positive ones, because the leftmost bit by itself is already the most negative number.

Definition 4.3.1(range of n-bit two's complement).

An $n$ -bit pattern read as a two's complement number can stand for every whole number from $-2^{n-1}$ up to $2^{n-1}-1$ . For four bits that is the range on the wheel above.

The bits do not say which reading is meant. The circuit that adds two patterns is the same whether you think of them as signed or as unsigned, and the table below shows one addition read both ways.

4-bit A + B: A is 0010, B is 1100; result 1110, 14 unsigned, -2 signed
	4-bit pattern	unsigned	signed
A	0010	2	2
+ B	1100	12	-4
=	1110	14	-2

The result row has one bit pattern with two values. Reading the same bits as signed or as unsigned decides what the answer means, and the next section deals with when each answer is still right.

Negation

Definition 4.3.2(negation in two's complement).

To negate a two's complement number, invert every bit and then add 1: the negation of $x$ is $\overline{x}+1$ , written ~x + 1 in SystemVerilog.

Why does that work? A pattern and its bitwise inverse have a 1 in exactly one of the two for every position, so adding them gives a pattern of all 1s. Adding 1 to all 1s wraps the dial around to 0, so $x + (\overline{x}+1)$ is 0 in $n$ bits. The number that you add to $x$ to get 0 is exactly what is meant by $-x$ .

Example 4.3.1(negating 3, 0 and −8 in four bits).

Take the pattern 0011, the number 3. Inverting gives 1100, and adding 1 gives 1101.

4-bit negate A: A is 0011; result 1101, 13 unsigned, -3 signed; carry 0; overflow 0
	4-bit pattern	signed
A	0011	3
−A	1101	-3

carry = 0overflow = 0

The result is 1101, whose signed value is the negation of 3. Zero negates to itself, and the carry out of that addition is dropped:

4-bit negate A: A is 0000; result 0000, 0 unsigned, 0 signed; carry 1; overflow 0
	4-bit pattern	signed
A	0000	0
−A	0000	0

carry = 1overflow = 0

The pattern 1000, the most negative number, is different: inverting gives 0111, and adding 1 gives 1000 again.

4-bit negate A: A is 1000; result 1000, 8 unsigned, -8 signed; carry 0; overflow 1
	4-bit pattern	signed
A	1000	-8
−A	1000	-8

carry = 0overflow = 1

The negation of the most negative number is itself, and the overflow flag says that the answer is wrong: the true negation is $+8$ and four bits can only reach 7.

In SystemVerilog

A small module runs the same cases.

// Negation by the two's complement rule: flip every bit of x, then add one.
module negate4(
  input  logic [3:0] x,
  output logic [3:0] y
);
  assign y = ~x + 4'd1;
endmodule

// Negates a small value, zero, and the most negative four-bit value, whose negation does not exist.
module negate4_tb();
  logic [3:0] x, y;

  negate4 dut(.*);

  initial begin
    x = 4'b0011; #10;   // expect: y=4'b1101
    $display("DD x3=%0d", $signed(x));
    $display("DD y3=%0d", $signed(y));
    x = 4'b0000; #10;   // expect: y=4'b0000
    x = 4'b1000; #10;   // expect: y=4'b1000
    $display("DD x8=%0d", $signed(x));
    $display("DD y8=%0d", $signed(y));
    $stop;
  end
endmodule

For the pattern 0011 the simulation gives y = 1101, which as a signed value is -3, the negation of 3. For 1000 the output is 1000 again: x is -8 and so is y, -8. A separate program tried all sixteen patterns: for every x, adding y gives 0 in four bits, and y is the only pattern for which that is true.

In four-bit two's complement, what is the negation of −8?

-880

Subtraction

Negation turns subtraction into addition: $A-B$ is $A+(-B)$ , which is $A+\overline{B}+1$ . The adder needs no subtraction rule. It needs the second operand inverted, and a carry in of 1 at the right end, which is where the extra 1 is added. The final carry out of the top column is thrown away.

The four examples below are 4-bit additions and subtractions, each shown with both readings of every row. In the two additions the adder adds the patterns as they are. In the two subtractions the table's operation is the one given, and the flags are for the adder that does $A+\overline{B}+1$ .

Example 4.3.2(four 4-bit cases, read unsigned and signed).

4-bit A + B: A is 0010, B is 1100; result 1110, 14 unsigned, -2 signed; carry 0
	4-bit pattern	unsigned	signed
A	0010	2	2
+ B	1100	12	-4
=	1110	14	-2

carry = 0

Read as signed numbers this is 2 plus −4, which gives −2, and the pattern 1110 is −2. Read as unsigned numbers it is 2 plus 12, which gives 14, and 1110 is 14 as well. The same bits are right under both readings.

4-bit A + B: A is 1000, B is 0100; result 1100, 12 unsigned, -4 signed; carry 0
	4-bit pattern	unsigned	signed
A	1000	8	-8
+ B	0100	4	4
=	1100	12	-4

carry = 0

This is −8 plus 4, which gives −4, and 8 plus 4, which gives 12; the pattern 1100 is both.

4-bit A − B: A is 0110, B is 0010; result 0100, 4 unsigned, 4 signed; carry 1
	4-bit pattern	unsigned	signed
A	0110	6	6
− B	0010	2	2
=	0100	4	4

carry = 1

For the subtraction, the adder computes 0110 + 1101 + 1, which is 10100 in five bits. The top bit is the final carry out, and it is thrown away: four bits remain, 0100. That is 6 minus 2.

4-bit A − B: A is 1111, B is 1110; result 0001, 1 unsigned, 1 signed; carry 1
	4-bit pattern	unsigned	signed
A	1111	15	-1
− B	1110	14	-2
=	0001	1	1

carry = 1

Here the signed reading is −1 minus −2, which is 1, and the unsigned reading is 15 minus 14, which is also 1. Both readings agree again.

The carry row in these tables is not explained here, and the signed and unsigned results do not agree for every pair of operands. Section 4.4 treats both.

Widening a number

Two's complement numbers often have to be put in a wider signal before they are added. Section 2.6 introduced the two ways, zero padding and sign extension (Definition 2.6.2), and showed that each preserves one reading. For arithmetic the rule is plain: a signed value must be sign-extended, and an unsigned value zero-extended. The adder does not know which you meant.

// Adds two 4-bit numbers into an 8-bit result, widening the inputs first. sum_sext keeps the signed values and sum_zext keeps the unsigned values.
module widen_add(
  input  logic [3:0] a,
  input  logic [3:0] b,
  output logic [7:0] sum_sext,
  output logic [7:0] sum_zext
);
  assign sum_sext = {{4{a[3]}}, a} + {{4{b[3]}}, b};
  assign sum_zext = {4'b0000, a} + {4'b0000, b};
endmodule

The module adds two 4-bit numbers into 8 bits. It gives the answer for both choices of widening. The testbench adds the patterns 1110 and 0011, which are −2 and 3 as signed numbers.

// Adds -2 and 3, then -2 and -3, with both ways of widening. Only sign extension gives the signed sum.
module widen_add_tb();
  logic [3:0] a, b;
  logic [7:0] sum_sext, sum_zext;

  widen_add dut(.*);

  initial begin
    a = 4'b1110; b = 4'b0011; #10;   // expect: sum_sext=8'b00000001, sum_zext=8'b00010001
    $display("DD pos_sext=%0d", $signed(sum_sext));
    $display("DD pos_zext=%0d", $signed(sum_zext));
    a = 4'b1110; b = 4'b1101; #10;   // expect: sum_sext=8'b11111011, sum_zext=8'b00011011
    $display("DD neg_sext=%0d", $signed(sum_sext));
    $display("DD neg_zext=%0d", $signed(sum_zext));
    $stop;
  end
endmodule

With sign extension the sum is 1, which is $-2+3$ . With zero padding it is 17, which is what you get by reading 1110 as 14. Adding 1110 and 1101, −2 and −3, gives -5 with sign extension and 27 with zero padding, each read as a signed 8-bit number. A program tried all 256 pairs of 4-bit inputs and checked that the sign-extended output is always the sum of the signed values, and the zero-padded output the sum of the unsigned values.

Course conventions

How CSE 369 writes this

Lecture 4 states the negation rule as ~x + 1 == -x^{F (fact ch04/twos-rules)}, writes subtraction as A − B = A + (−B) = A + (~B + 1), and notes that the last carry out is thrown away^{F (fact ch04/twos-sub-rule)}. The book uses the same rules.

Pitfalls

Common pitfall

Negating by flipping only the sign bit. That adds or removes $2^{n-1}$ instead of negating, and it gives the right pattern only by accident (0100 and 1100 in four bits); only inverting every bit and adding 1 gives the number that adds up to zero.
Forgetting the 1. Inverting every bit gives a number that is one less than the negation.
Expecting every value to have a negation. In $n$ bits the most negative number has none, and negating it gives it back.
Widening a signed value with zeros, or an unsigned value with copies of its leftmost bit. Pick the extension that matches the reading.
Reading the same pattern both ways in one calculation. Decide, for each signal, whether it is signed or unsigned, and keep to it.

Check your understanding

Take the quiz (5 questions)

Exercises

Exercise 4.3.1

The 8-bit pattern 10110100 is read as a signed number. What is its value? Check by negating it.

Hint

The leftmost bit is set, so the value is negative. Negating a negative number gives its size.

Solution

The leftmost bit is 1, so the value is negative. By the weights, $-128+32+16+4=-76$ . As a check, negate the pattern: invert every bit and add 1. The table shows the pattern and its negation, 01001100, which is 76.

8-bit negate A: A is 10110100; result 01001100, 76 unsigned, 76 signed
	8-bit pattern	unsigned	signed
A	10110100	180	-76
−A	01001100	76	76

The operand row shows the signed value of 10110100, and the result row, which is the negation, is the same number with its sign changed. The size of the number is read from the result row, so the pattern is the negative of the result row's value.

Tags: Warm-upNumber representationArithmetic

Exercise 4.3.2

Negate each of the 4-bit patterns 0101, 1001 and 0000, and give the signed value of each answer.

Hint

Invert each bit, add 1, and drop any carry out of the top bit.

Solution

For 0101, inverting gives 1010 and adding 1 gives 1011.

4-bit negate A: A is 0101; result 1011, 11 unsigned, -5 signed
	4-bit pattern	signed
A	0101	5
−A	1011	-5

For 1001, inverting gives 0110 and adding 1 gives 0111.

4-bit negate A: A is 1001; result 0111, 7 unsigned, 7 signed
	4-bit pattern	signed
A	1001	-7
−A	0111	7

For 0000, inverting gives 1111 and adding 1 gives 10000, whose fifth bit is dropped, so the answer is 0000.

4-bit negate A: A is 0000; result 0000, 0 unsigned, 0 signed; carry 1
	4-bit pattern	signed
A	0000	0
−A	0000	0

carry = 1

The carry out of the last one is the dropped fifth bit.

Tags: Warm-upNumber representationArithmetic

Exercise 4.3.3

Compute 0011 − 0101 in 4 bits as an addition: invert the second operand, add it to the first with a carry in of 1, and discard the carry out. Give the result and its signed value.

Hint

The inverted second operand is 1010. Add it to 0011 and then add the carry in.

Solution

The second operand 0101 inverts to 1010. Adding the first operand and then the carry in of 1: 0011 + 1010 is 1101, and 1101 + 1 is 1110.

4-bit A − B: A is 0011, B is 0101; result 1110, 14 unsigned, -2 signed; carry 0
	4-bit pattern	unsigned	signed
A	0011	3	3
− B	0101	5	5
=	1110	14	-2

carry = 0

The result row agrees: 1110, which is the signed number −2, as $3-5$ should be.

Tags: StandardNumber representationArithmetic

Exercise 4.3.4

A 4-bit signed value 1010 is added to the 8-bit signed value 00000111. Widen the first operand correctly, add, and give the signed result. Then widen it the wrong way and add, to see what goes wrong.

Hint

The 4-bit pattern 1010 has a leftmost bit of 1. Which bits go in front of it to keep its signed value?

Solution

Sign extension copies the leftmost bit, 1, into the four new positions, so 1010 becomes 11111010.

8-bit A + B: A is 11111010, B is 00000111; result 00000001, 1 unsigned, 1 signed
	8-bit pattern	unsigned	signed
A	11111010	250	-6
+ B	00000111	7	7
=	00000001	1	1

The signed row of the first operand is the value of the 4-bit pattern, unchanged by the widening, and the result is its sum with the second operand. With zero padding, 1010 would become 00001010 and the sum would be a different number:

8-bit A + B: A is 00001010, B is 00000111; result 00010001, 17 unsigned, 17 signed
	8-bit pattern	unsigned	signed
A	00001010	10	10
+ B	00000111	7	7
=	00010001	17	17

Zero padding turned the first operand into the unsigned value of the pattern, so the result is the sum of that value and the second operand. It is not what the signed values add up to.

Tags: StandardNumber representationArithmetic

Exercise 4.3.5

Which 4-bit patterns are their own negation?

Hint

A pattern that equals its own negation satisfies

x + x = 0

in 4 bits. Which numbers added to themselves make a multiple of 16?

Solution

The negation $y$ of $x$ is the one pattern with $x+y=0$ in four bits. If $y=x$ then $2x$ must be a multiple of $2^4$ , so $x$ is a multiple of $2^3$ , and there are two such patterns: 0000 and 1000. Both appear in the tables below:

4-bit negate A: A is 0000; result 0000, 0 unsigned, 0 signed; carry 1; overflow 0
	4-bit pattern	signed
A	0000	0
−A	0000	0

carry = 1overflow = 0

4-bit negate A: A is 1000; result 1000, 8 unsigned, -8 signed; carry 0; overflow 1
	4-bit pattern	signed
A	1000	-8
−A	1000	-8

carry = 0overflow = 1

Zero negates to zero because adding 1 to the inverted pattern carries all the way out and leaves 0000. The most negative number negates to itself because its true negation does not fit, which is what the overflow flag of the second table reports. Every other pattern has a negation that differs from it.

Tags: ChallengeNumber representationArithmetic