Binary Arithmetic with Two's Complement

Hello and welcome to your first lesson. We're embarking on a journey to understand how modern digital systems are built, from the fundamental level of binary logic all the way up to complex microcontrollers. Your goal is to see "how every dot connects," and this course is designed to do just that, starting from the ground up.

In this introductory lesson, we will tackle a foundational concept: how computers perform arithmetic. Since all information in a digital circuit is represented by binary digits (bits), we need a system to handle not just positive numbers, but negative ones as well. You'll learn how to perform binary addition and subtraction using the universal standard for this task: two's complement representation. Mastering this is the first essential step toward designing the arithmetic circuits that form the heart of every processor.

The Challenge of Negative Numbers

At its core, a computer only works with 0s and 1s. This is sufficient for representing positive integers, but what about negative values? How do we express a concept like "-5" using only bits?

A natural first thought might be to reserve one bit—typically the most significant bit (MSB)—to act as a sign. For example, '0' for positive and '1' for negative. This is called sign-magnitude representation. While intuitive, it has significant drawbacks, including two different representations for zero (+0 and -0) and, more critically, it makes arithmetic circuitry complicated and inefficient.

A slightly better approach, called one's complement, involves simply inverting all the bits of a positive number to get its negative counterpart. This solves some arithmetic problems but still suffers from having a negative zero.

The video below, from the excellent Ben Eater channel, provides a clear demonstration of these earlier methods and illustrates why they fall short. This will help you appreciate the elegance of the solution that the industry ultimately adopted.

As you saw, both simple approaches are flawed. This leads us to the universal standard used in virtually all modern computers: two's complement.

Two's Complement Representation

Two's complement provides an elegant way to represent signed integers that eliminates the problems of negative zero and, most importantly, allows subtraction to be performed using the exact same hardware as addition.

The rule for finding the two's complement negative of a number is simple:

1. Take the positive binary representation of the number.
2. Invert all the bits (change 0s to 1s and 1s to 0s). This step is also known as taking the one's complement.
3. Add 1 to the result.

Let's solidify this with a textual resource and another look at the Ben Eater video.

Now, let's see this process in action and understand why it solves the issues we saw earlier.

Binary Arithmetic with Two's Complement

The primary benefit of two's complement is that it unifies addition and subtraction. The operation A - B is simply computed as A + (-B), where -B is the two's complement of B. This means a processor doesn't need a separate "subtractor" circuit; it can use its adder for both operations.

First, let's ensure you're comfortable with standard binary addition, especially the concept of carrying over.

Now that we have the two's complement representation for negative numbers and a solid grasp of binary addition, we can perform subtraction.

The image below shows a simple subtraction, $17-10$. Notice how it's transformed into an addition: $17+(-10)$. The binary for 10 is converted to its 8-bit two's complement representation, and then the two numbers are added. The final carry bit (the 9th bit) is discarded because we are working with 8-bit numbers.

Overflow

A crucial concept in computer arithmetic is overflow. Because computers store numbers in fixed-size chunks (e.g., 4-bit, 8-bit, 32-bit), the result of an operation can sometimes be too large (or too small) to fit.

For an N-bit two's complement number, the range of values that can be represented is from $-2^{N-1}$ to $2^{N-1}-1$. For example, with 4 bits, the range is -8 to +7.

Overflow occurs under two conditions:

1. Adding two positive numbers results in a negative number.
2. Adding two negative numbers results in a positive number.

Note that adding a positive and a negative number can never cause an overflow.

The image below shows several examples of 4-bit two's complement addition. Examples (e) and (f) demonstrate overflow. In (e), adding two positive numbers (5 + 4) yields a result that is interpreted as -7. In (f), adding two negative numbers (-7 + -6) yields a result interpreted as +3. Both are incorrect due to overflow.

How does a computer detect this? There is a simple hardware-level rule: An overflow has occurred if the carry-in to the most significant bit (MSB) column is different from the carry-out of the MSB column.

Let's watch a video that ties together the arithmetic process and the overflow condition.

Why Does "Invert and Add One" Work?

You've expressed a desire to understand not just the "how" but also the "why." The "invert and add one" rule can seem like a bit of mathematical magic, but it has a solid logical foundation.

Thinking in base 10, the negative of a number $x$ can be thought of as $0-x$. If we do this with borrowing, we find a pattern. A similar pattern emerges in binary. The negative of an n-bit number $B$ is mathematically equivalent to $2^n-B$.

It turns out that $2^n-B$ can be rewritten as $((2^n-1)-B)+1$. In binary, $2^n-1$ is just a string of n ones (e.g., for n=8, it's 11111111). Subtracting a binary number $B$ from a string of all 1s is the same as inverting all the bits of $B$.

So, the operation simplifies to: (invert all bits of $B$) + 1. This is precisely the two's complement rule.

This connection between a high-level mathematical concept (negation) and a simple bit-level operation (inversion and addition) is a perfect example of the link between theory and hardware implementation that we will explore throughout this course.

Conclusion

In this lesson, we have laid the very first stone in our foundation. You've learned not just how to perform binary arithmetic, but why it's done the way it is.

Here are the key takeaways:

• Computers represent signed numbers using a fixed number of bits, most commonly with the two's complement system.
• To find the negative of a number, you invert all the bits and add one.
• The great advantage of two's complement is that subtraction is performed as addition: A - B becomes A + (-B). This simplifies hardware design.
• Overflow occurs when the result of an operation is outside the representable range for the given number of bits. It can be detected by checking if the carry-in and carry-out of the final bit are different.

In our next lesson, we will move one step deeper into the logic of digital circuits by exploring Boolean algebra. This is the mathematical language used to describe and manipulate the logic gates that will ultimately build the adders we've discussed today.