We know that computers can store booleans quite easily using high and low voltage currents. How does that translate into being able to achieve all of the wonderful things we can do with computers, though? In this section, we are going to take everything we have seen so far to create an adding machine using only booleans.
First, we need to refresh on how addition works for multi-digit numbers. We’ve already looked at bitwise operators and how the OR/XOR operators can give us addition of single bits. But when we add larger numbers together, we need to use carry-over bits as well.
| 1 | ||
| 2 | 8 | |
| + | 2 | 3 |
| 5 | 1 |
Carryover bits work the exact same way in binary as they do in decimal like you’re used to (as in the example above). Because 8 + 3 ≥ 10 we keep the 1’s digit from the sum and “carry” the 10 to the next place. Similarly, we carry a 10 (that’s a two in binary!) over whenever the sum of two bits is greater than or equal to 2.
| 1 | ||
| 0 | 1 | |
| + | 0 | 1 |
| 1 | 0 |
With that in mind, let’s think about how we would add two single-digit binary numbers together. Our goal is to have a function that takes two booleans as input (representing the two bits we’re adding) and outputs two new booleans representing the sum digit and the carry digit. The values of the sum bit and the carry bit should match up with what happens when we add two bits together, shown in the table below.
| Input A | Input B | Carry Bit | Sum Bit |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
This should hopefully remind you of a truth table! Try to write out the boolean statements that would give you the correct outputs. Note that you will need two boolean statements (one for the carry, one for the sum) as each of them can only output a single value.
Once you have a boolean logic statement, try to draw out a logic gate diagram that achieves the correct outputs. Your diagram should have two input wires, A and B, and two output wires, S (sum) and C (carry).
This is called a half-adder because it is basically half of the logic necessary for full addition. When we cascade our addition for larger numbers, we don’t have just two bits to add…but rather three! (The A and B still, but then the C carry from the previous addition!) As such, we need to modify our logic to accommodate the full addition. First things first, we need to plan out the inputs and outputs. Fill in the table with the appropriate values for the two output bits.
| A | B | C-IN | C-OUT | S |
|---|---|---|---|---|
| 1 | 1 | 1 | ||
| 1 | 1 | 0 | ||
| 1 | 0 | 1 | ||
| 1 | 0 | 0 | ||
| 0 | 1 | 1 | ||
| 0 | 1 | 0 | ||
| 0 | 0 | 1 | ||
| 0 | 0 | 0 |
Now that we know what the output bits should be, we have the more difficult task of determining what set of logic will give the appropriate output. Once again try to write out the logical statements for each output bit as well as draw the gate diagrams.
These are established logical patterns, but don’t just look up the logic on the internet. That ruins the worthwhile exercise of challenging yourself to solve a problem.
With the necessary logic planned out, the time has come to try to implement the adder using Java! We need a function that accepts three boolean inputs and outputs two booleans. Since we cannot make a function that actually outputs two different values, we will use a return type of boolean[] (a boolean array) so that we can indeed have two separate values output. Hopefully you find that with the logic planned out, writing the code isn’t actually that difficult.
← Previous PageNext Page →