Binary Subtraction and Two's Complement

A while ago, I talked about how to use Boolean algebra to add two binary numbers. Now I'm going to show you how you can do subtraction in a similar way.

To start with, I'm going to ignore negative numbers. I'll get to those later, but for now, for simplicity's sake, I'm going to assume the first number will always be larger than the second, so the answer will always be positive.

Let's start again with 1-bit numbers. 1-1=0, 1-0=1, 0-0=0, so we have this truth table:

X	Y		Z
0	0		0
0	1		?
1	0		1
1	1		0

The question mark is to denote a value that can be either 1 or 0. We don't care about that particular value, because it would be negative. Because of that value, there are two functions that satisfy this truth table: X XOR Y, and X AND ¬Y.

Extending this to multiple digits is similar to extending addition to multiple bits, but instead of sometimes needing to carry, we'll sometimes need to borrow. The difference between carrying and borrowing is that instead of adding one to the next digit to the left, you subtract one from the next digit to the left, and you borrow in cases where the result would be less than 0, instead of greater than 1.

X	Y	BN-1		Z	BN
0	0	0		0	0
0	0	1		1	1
0	1	0		1	1
0	1	1		0	1
1	0	0		1	0
1	0	1		0	0
1	1	0		0	0
1	1	1		1	1

B_N-1 indicates whether a borrow was required for the digit to the right of the current one, and B_N indicates whether the current digit requires a borrow. For the rightmost digit, B_N-1 is 0.

So, Z = X XOR Y XOR B_N-1, and B_N = (¬X AND Y) OR (¬X AND B_N-1) OR (Y AND B_N-1)

Now, what about negative numbers? For that matter, how do we even represent negative numbers? Computers only have 1 and 0, there's no -.

Well, there are a number of ways you could do that. You could for example designate one bit to be a sign bit, where one value indicates positive, and the other negative. Normally, the sign bit is the leftmost digit, and normally 0 indicates positive. So, 0101 would be 5, while 1101 would be -5.

This particular method has the disadvantage of wasting a number, because 000 and 100 represent 0 and -0, which are equal. It also requires different algorithms for adding and subtracting negative numbers.

Wouldn't it be nice if there were a representation of negative numbers that allowed the use of the same algorithms for both positive and negative numbers? Well, there is one, it's called two's complement.

It's not very intuitive, but it's very convenient for doing these bitwise functions. Like the method I just described, the leftmost digit is a sign bit, and 0 represents positive. But instead of the rest of the bits being the same as the positive representation, you flip all the bits, and then add 1.

0101 would still be 5. To get the bits for -5, first start by replacing every 1 with a 0, and every 0 with a 1, so we get 1010. Then add 1, so we get 1011. If the rightmost digit is 1, it carries the way you would expect, so -3 ⇒ 0100 ⇒ 1011 ⇒ 1100.

Notice what happens when you try to represent -0 like before. 0000 ⇒ 1111 ⇒ 0000. So, there's only one possible representation of 0. 1000 would represent -8. In general, with N bits, the highest number you can represent is 2^N-1-1, and the lowest is -2^N-1

When you use two's complement, you can use exactly the same algorithm I described above to subtract with both positive and negative numbers. You can also add using the same algorithm I described in my previous post.

Binary Addition

Before, I talked about how to use binary to represent a number using only two values. But what if you want to actually do something with those numbers? How do you add numbers using Boolean operations?

Well, let's start with a simple case: adding two one-bit numbers. We'll call them X and Y, and since they each only have one binary digit they can only have the values 0 or 1. So here are the cases we need to account for: 0+0=0, 0+1=1, 1+0=1, 1+1=10.

Notice the answer for that final case has two digits. A Boolean function can only return one value, so how can get that? By having two functions, one for each digit.

So, the function for the rightmost digit has to satisfy this truth table:

X	Y		Z0
0	0		0
0	1		1
1	0		1
1	1		0

What Boolean operation does that look like? XOR.

The function for the next digit will have to satisfy this truth table:

X	Y		Z1
0	0		0
0	1		0
1	0		0
1	1		1

That's the same as the AND operation.

I'm using the subscripts here to indicate which digit in the overall number. So our two bit answer Z has the individual bits Z₁Z₀, where Z₁ = X AND Y, and Z₀ = X XOR Y;

So, that's how you can add two one-bit numbers. But what if you want to add bigger numbers? Well, the way you add the second bits together is pretty much the same as the first bits, with one major difference: You need to account for the bit that got carried from the sum of the first bits. If that carry bit was 0, then the result of the next bit will be same as the first. But if it's one, then the result is increased by one. So, 0+0+1=1, 0+1+1=10, 1+0+1=10, 1+1+1=11.
So, now we have these two truth tables:

X1	Y1	C		Z1
0	0	0		0
0	1	0		1
1	0	0		1
1	1	0		0
0	0	1		1
0	1	1		0
1	0	1		0
1	1	1		1

X1	Y1	C		Z2
0	0	0		0
0	1	0		0
1	0	0		0
1	1	0		1
0	0	1		0
0	1	1		1
1	0	1		1
1	1	1		1

So, Z₁ = X₁ XOR Y₁ XOR C and Z₂ = (X₁ AND Y₁) OR (X₁ AND C) OR (Y₁ AND C). C, the carry bit, comes from the second bit of the result of the sum of the first two bits, that is C = X₀ AND Y₀.

Each subsequent bit works just like the second, with the second bit of the previous result being carried over. Generally, and Z_n = (X_n AND Y_n) OR (X_n AND C_n-1) OR (Y_n AND C_n-1), and C_n = X_n XOR Y_n XOR C_n-1.

Here's another challenge for you: How do you do subtraction in a similar manner?

Binary

Before, I talked about some of the things computers can do using only two values. But what about numbers? How can computers do arithmetic with only 0s and 1s? The answer to that question is "binary". If you already know what binary is, this post will just be a refresher.

Before I begin explaining binary, let's go over how the number system we normally use, that is, base ten, works. How do you count? How do you determine what the next number is?

Well, you start with 0, which is followed by 1, then 2, 3, 4, 5, 6, 7, 8 and 9. You pretty much just have to memorize that sequence. But what comes after 9? 10. That's interesting. It's not just another symbol, it's two symbols, and two symbols we've seen before.

Let's continue. After 10 comes 11, 12, 13, 14, 15, 16, 17, 18, 19. Hey, that looks familiar. Those numbers are the same as the first ten, except with a 1 on the front of each of them. And what comes after 19? 20. And the same sequence as before will repeat again, except with a 2 on the front, instead of a 1. And after that comes 30. And then, the same sequence will repeat again, but with a 3 this time.

Hey, wait a minute. The number on the front is itself going through that sequence too, it's just waiting for the second number to cycle through before going to the next step. So, after 30 comes 40, then 50, 60, 70, 80, 90.

So, what comes after 99? 100. Another symbol got added, just like when 9 turned into 10. And that's all there is to counting. You can continue following these same steps forever, and you'll never run out of numbers. Let's write out these steps a little more explicitly.

First, you have to memorize a sequence of symbols: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].
Then, to get the next number after the current one, replace the rightmost digit with the next symbol in the sequence. If it's already at the last symbol, then set it back to the beginning of the sequence, and repeat the last step for the next digit to the left. If there is no digit to the left, it's implied to be 0, so 1 is added.

But notice, there's nothing special about that sequence of symbols. You could follow the same rules using any sequence of symbols. For example, you could use this sequence: [a, b, c, d]. Then you would count a, b, c, d, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd, baa...

Or you could use this sequence: [0, 1]. Then you would count 0, 1, 10, 11, 100, 101, 110, 111, 1000...

And that's what binary is. Counting, with only 0 and 1.

What if you want to convert from one base to another? If you have a number in base ten, and want to know how it's written in binary, or the other way around?

Well, one way to do that is just to count. Numbers are the same, regardless of how they're written, so if you count up the same number, it will be the same in every base.

Base ten	0	1	2	3	4	5	6	7	8	9	10	11	12
Binary	0	1	10	11	100	101	110	111	1000	1001	1010	1011	1100

But that's going to be cumbersome for large numbers. Is there an easier way?

Yes, there is. Notice, that in any base, the number 10 represents the number of symbols in the sequence you're using. There are ten symbols in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], and 10 represents ten. There are two symbols in [0, 1] and 10 in binary represents two. That's not a coincidence, and I trust you're smart enough to figure out why that is.

A consequence of that is that the number 100 in any base is going to be equal to the number of symbols times itself. 10*10 = 100. And this gives you the concept of "place". You know, the digit furthest to the right is the ones place, the next digit to the left is the tens place, the next digit to the left is the hundreds place and so on.

That concept applies to any base. The rightmost digit will always be the ones place. The digit there stands for itself. The next digit to the left will be multiplied by the base. Each further digit to the left will be multiplied by the base again. So in binary, you get the ones place, the twos place, the fours place, the eights place, and so on.

So, for example, let's try that on this binary number: 101011
The rightmost digit is 1, and it's in the ones place, so it's equal to 1.
The next digit is 1, and it's in the twos place so it's 1*2 = 2.
The next digit is in the fours place, but it's 0, and 0 times anything is still 0, so it's 0.
The next digit is 1, and it's in the eights place, so it's 8.
The next digit is in the sixteens place, but it's 0.
The next digit is in the thirty-twos place, so it's 32.
So, the value is 32 + 8 + 2 + 1 = 43.

What about the other way? Converting a number from base ten to binary? That's a little bit harder to describe, so I'll explain with an example. Say we're converting the number 57. What we need to do is divide that number by 2 and find the remainder. 57 / 2 = 28 remainder 1. The remainder is the rightmost digit of our binary number.
To continue we need to divide 28. 28 / 2 = 14 remainder 0. The next digit in our binary number is 0.
14 / 2 = 7 remainder 0.
7 / 2 = 3 remainder 1.
3 / 2 = 1 remainder 1.
1 / 2 = 0 remainder 1.
So our binary number is 111001.

In other words, in each step you need to divide your number by two. The remainder is the next digit of the binary number, starting from the right and going left. You're done when the result of the division is zero.

And that is how you can represent numbers, using only 0 and 1.

De Morgan's Law and Duality

Before, I gave the challenge of replicating the boolean OR function using only NANDs (and replicating AND using only NORs). I'm going to show you the solution, using truth tables. A truth table is a table where you list out every possible combination of values of the inputs, and the corresponding value of the output. Here's a truth table showing the AND, OR, NAND and NOR functions.

X	Y		X∧Y	X∨Y	X NAND Y	X NOR Y
F	F		F	F	T	T
F	T		F	T	T	F
T	F		F	T	T	F
T	T		T	T	F	F

You can show that two functions are equivalent by showing that they have the same output as each other for every possible combination of inputs. Here's a simple example to show that ¬X = X NAND X.

X		¬X	X NAND X
F		T	T
T		F	F

If you're not sure what one of the outputs should be, plug in the input values and evaluate it. F NAND F = T, and T NAND T = F, which you can see from the first truth table.

So, here's the solution to the first part of the challenge: X∨Y = (X NAND X) NAND (Y NAND). Here's the truth table.

X	Y		X NAND X	Y NAND Y	(X NAND X) NAND (Y NAND Y)
F	F		F NAND F = T	F NAND F = T	T NAND T = F
F	T		F NAND F = T	T NAND T = F	T NAND F = T
T	F		T NAND T = F	F NAND F = T	F NAND T = T
T	T		T NAND T = F	T NAND T = F	F NAND F = T

Try to figure out the second part of the challenge (That is replicate the AND function using only NOR) using a truth table now. I'll wait.

.

.

.

.

.

.

.

.

The solution to the second part is X∧Y = (X NOR X) NOR (Y NOR Y). Interestingly, it's exactly the same as the first part, except with ∨ replaced by ∧ and NAND replaced by NOR. I'll talk about that more in a bit, but first notice that since (X NAND X) = ¬X, the solution to the first part can be rewritten as X∨Y = ¬X NAND ¬Y. Also, since (X NAND Y) = ¬(X∧Y), it can be further changed to X∨Y = ¬(¬X∧¬Y). The same way, the solution to the second part can be rewritten as X∧Y = ¬(¬X∨¬Y).

This is an example of De Morgan's Law, which says that ¬(X∧Y) = ¬X∨¬Y and ¬(X∨Y) = ¬X∧¬Y. De Morgan's Law is a very important thing to remember when doing Boolean algebra. It's a useful way of simplifying expressions, and it's vital for programmers to know.

De Morgan's Law also ties back into the other point I made. Notice that the two forms of De Morgan's Law are the same, except with ∧ and ∨ swapped? In fact, you can take any boolean expression, swap ∧ and ∨, and swap T and F, and the expression will mean the same thing.* For example, X∧T=X, swapped X∨F=X. Also, X∧F=F, swapped X∨T=T. This property is called duality.

Why does this happen? Keep in mind that the labels we use are arbitrary. It doesn't matter if we use T and F or 1 and 0, or if we use ∧ and ∨ or AND and OR. What matters is the relationships that hold between the symbols. And the way we've defined them, the relationships between T and ∧ are exactly the same as the relationships between F and ∨. That is, X AND Y is true if and only if both X and Y are true. X OR Y is false if and only if both X and Y are false. Those say exactly the same things, just with the names changed.

*If the expression contains XOR, or other functions besides ∧, ∨ and ¬, those need to be rewritten to use only ∧, ∨ and ¬. Or they can be swapped with their own dual, for example, the dual of XOR is XNOR. ¬ is it's own dual.

Boolean Algebra

You may have heard that computers only use the numbers 0 and 1. It's true. Everything computers do is done using electronic switches, and those switches can only be either on or off. (That's not strictly necessary. It's possible to make an electronic switch that has in-between states, but on/off is the simplest and easiest way to make a switch.) But how can computers calculate larger numbers or do all the cool things computers do, if they can only use 0 and 1? Well, one of the fundamental ideas behind how computers work is Boolean algebra.

Boolean algebra is a type of math that only uses two values. These two values are usually called true and false, or 1 and 0. There are three basic operations of Boolean algebra.

NOT X, also written as ¬X is simply the opposite of X. If X is true, ¬X is false. If X is false ¬X is true. Unsurprisingly, ¬¬X=X.

X AND Y, also written as X∧Y is true if both X and Y are true. Otherwise, it's false. The AND operation is also sometimes written as multiplication, because it works the same way. 0*0=0, 0*1=0 and 1*1=1. And just as with multiplication X*0=0 and X*1=X, no matter what X is, X∧F=F and X∧T=X, no matter what X is.

X OR Y, also written as X∨Y is true if X is true, Y is true or both are true. The OR function is sometimes written as addition. Similar to normal addition, 0+0=0, 0+1=1 and 1+1=... Well, there's no 2, so 1+1=1. This has the properties that X∨F=X, just like X+0=X, and X∨T=T, unlike normal addition.

You can put these operations together to get more complicated operations. For example X XOR Y, also written as X⊕Y, is true if X is true, or Y is true, but not both. It can be built out of the other operations like this (X∨Y)∧¬(X∧Y). Similarly, NAND, NOR and XNOR are made by putting a NOT in front of an AND, OR and XOR, respectively.

Although I said there are three basic operations of Boolean algebra, there really only needs to be one. You can make every single Boolean operation out of just NAND or just NOR. For example, ¬X = X NAND X. X∧Y = ¬(X NAND Y) = (X NAND Y) NAND (X NAND Y).

Here's a challenge for you: How can you make the OR operation, using or NAND, or complementarily, how can you make AND using only NOR?