L12: Signed Arithmetic

Where we learn about negative numbers.

Objective
Develop a basic understanding of addition and subtraction of signed Boolean values.

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Before the Lecture

Required Textbook Reading:

• 3.3 (Signed Numbers)

Optional Supplemental Instruction:

• Binary Addition and Subtraction With Negative Numbers, 2’s Complements & Signed Magnitude – The Organic Chemistry Tutor on YouTube
• Binary: Plusses & Minuses (Why We Use Two’s Complement) – Computerphile on YouTube

Negative Numbers in Binary

Representing negative numbers in binary requires choosing a method to encode the sign and magnitude. Here are the three most common approaches:

Sign and Magnitude Representation

Sign and magnitude is the most intuitive method: the leftmost bit (most significant bit) indicates the sign, while the remaining bits represent the absolute value.

How It Works

In an 8-bit sign and magnitude system:

• Leftmost bit = 0: positive number
• Leftmost bit = 1: negative number
• Remaining 7 bits: magnitude (absolute value)

Examples

Limitations

Two representations of zero: Both 00000000 (+0) and 10000000 (-0) represent zero, which wastes a value and complicates comparisons. Arithmetic complexity: Adding numbers requires checking the sign bits first and choosing between addition or subtraction, making hardware implementation inefficient.

1’s Complement Representation

1’s complement inverts all bits of a number to negate it. To find the negative of any number, flip every 0 to 1 and every 1 to 0.

How It Works

For an 8-bit system, to negate a number, perform a bitwise NOT operation on all bits.

Examples

Addition in 1’s Complement

1’s complement allows simple addition: add numbers as normal, and if there’s a carry out from the sign bit, add 1 back to the least significant bit (called an “end-around carry”).

Example: 5 + (-3) in 8-bit 1’s complement

  00000101  (+5)
+ 11111100  (-3)
-----------
 100000001  (carry out)
  00000001  (add carry back: 1 + 1)
  00000010  (+2) ✓

Limitations

Two representations of zero: Like sign and magnitude, 1’s complement has both 00000000 and 11111111 as zero. Less efficient arithmetic: The end-around carry adds complexity to hardware adders.

2’s Complement Representation

2’s complement is the standard method used in modern computers. To negate a number, invert all bits and add 1 (equivalent to: find the 1’s complement, then add 1).

How It Works

For any n-bit system, 2’s complement represents values from -2^(n-1) to 2^(n-1) - 1. The range is asymmetric: there’s one more negative value than positive.

Examples

Addition in 2’s Complement

2’s complement allows straightforward binary addition with no special handling: simply add the numbers and ignore any carry out from the sign bit. The result is automatically correct.

Example: 5 + (-3) in 8-bit 2’s complement

  00000101  (+5)
+ 11111101  (-3)
-----------
 100000010  (ignore carry out)
  00000010  (+2) ✓

Example: -5 + (-3) in 8-bit 2’s complement

  11111011  (-5)
+ 11111101  (-3)
-----------
 111111000  (ignore carry out)
  11111000  (-8) ✓

Why 2’s Complement Is Superior

Single zero representation: Only 00000000 represents zero. Efficient arithmetic: Addition and subtraction work identically for positive and negative numbers; no special cases or end-around carries needed. Symmetric hardware: The same adder circuit handles all operations. Wider range: For n bits, you get one extra negative value (e.g., in 8 bits, -128 to +127 instead of -127 to +127).

Comparison Table

2’s complement has become the universal standard because it eliminates redundancy, simplifies hardware, and makes arithmetic operations uniform across all numbers.

Discussion & Practice
As a class, let’s make a table comparing the three approaches to negative numbers.

Adder and Subtractor Circuit

Subtracting two numbers in 2’s complement is elegant: to compute A - B, you negate B (convert it to its 2’s complement form) and add it to A. This insight allows us to build a subtractor using the same adder hardware by cleverly negating the subtrahend with XOR gates and a control signal.

The Key Insight: 2’s Complement Negation

Recall that to negate a number in 2’s complement, you flip all bits and add 1. We can decompose this into two operations:

1. Invert all bits (using XOR gates)
2. Add 1 (by setting the carry-in to 1)

This means we can control subtraction with just two modifications to a standard adder: XOR gates on the B input and a carry-in signal.

XOR Gates for Bit Inversion

An XOR (exclusive OR) gate has a special property: when one input is held constant, the other input is either passed through or inverted.

XOR Truth Table and Properties

When Input 2 = 0, the XOR acts as a buffer (output equals Input 1). When Input 2 = 1, the XOR acts as an inverter (output equals NOT Input 1).

How It Works

For Addition (Sub = 0):

• XOR gates pass B through: B’ = B
• Carry-in = 0
• Result: S = A + B ✓

For Subtraction (Sub = 1):

• XOR gates invert B: $B’ = B_\text{inverted}$ (1’s complement of B)
• Carry-in = 1 (effectively adds 1 to B)
• Result: $S = A + B_\text{inverted} + 1$ = A - B ✓ (2’s complement negation of B)

Step-by-Step Example: 5 - 3

Let’s trace through an 8-bit subtraction using this architecture.

Setting Up

A = 5  = 00000101
B = 3  = 00000011
Sub = 1 (subtraction mode)

Step 1: Invert B with XOR Gates

Each bit of B passes through an XOR gate with Sub = 1:

B[0] = 1,  XOR 1 = 0
B[1] = 1,  XOR 1 = 0
B[2] = 0,  XOR 1 = 1
B[3] = 0,  XOR 1 = 1
...
B' = 11111100 (1's complement of 3)

Step 2: Add with Carry-in = 1

Feed the inverted B’ and A into the adder with Cin = 1:

    00000101  (A = 5)
  + 11111100  (B' = NOT 3)
  +        1  (Cin = 1)
  -----------
    00000010  (S = 2) ✓

This is exactly 5 - 3 = 2.

Another Example: -3 - 5

Now let’s subtract with negative operands.

Setting Up

A = -3 = 11111101 (2's complement)
B = 5  = 00000101
Sub = 1

Step 1: Invert B

B = 00000101
B' = 11111010 (1's complement of 5)

Step 2: Add with Carry-in = 1

    11111101  (A = -3)
  + 11111010  (B' = NOT 5)
  +        1  (Cin = 1)
  -----------
   111111000  (ignore overflow carry)
    11111000  (S = -8) ✓

Indeed, -3 - 5 = -8.

Hardware Implementation

Gate Count

An n-bit add/sub unit requires:

• n XOR gates (one per bit of B)
• 1 n-bit adder (ripple-carry, carry-lookahead, or other design)
• 1 control signal (Sub)

Minimal Cost

This design is remarkably efficient: we add only n XOR gates and one control signal to a standard adder to gain subtraction capability. The XOR gates are among the simplest logic gates to implement.

Logic for the Carry-In

The carry-in is directly connected to the Sub control signal:

Cin = Sub

No additional logic is needed.

Overflow Detection

• Overflow occurs when adding two numbers with the same sign produces a result with a different sign
• Express this using the sign bits (MSBs) of $A$, $B$, and the result
• For a 4-bit system, $\text{overflow} = (A_3 \cdot B_3 \cdot \overline{S_3}) + (\overline{A_3} \cdot \overline{B_3} \cdot S_3)$

Discussion & Practice
As a class, let’s work through Examples 3.1–3.4 in the textbook.