Bitwise in Practice: Circuit Simulation
00:00 In the previous lesson, I showed you common uses of bit manipulation in code. In this lesson, I’m going to double down and show you a circuit simulation that uses all of these techniques together.
00:21 It’s a bit long and a bit abstract, so if you’re up for a challenge, stick around. I’m going to show you how to write some code that emulates how a digital circuit that does addition works. If you’ve had enough already, I won’t take it personally. Feel free to skip to the next lesson.
01:13 The first component I want to use is called a half adder. This adds two binary bits and has two outputs: one bit for the sum and one bit for the carry. If I add 0 and 1, the sum should be 1 and the carry 0. If I add 1 and 1, the single bit value overflows, so the sum line becomes 0 and the carry-out signals the overflow.
01:38 Alternatively, you can think of the carry-out as a second digit, but you’ll see why it’s called the carry-out in a minute. With a half adder in place, you can create a full adder. Like a half adder, a full adder takes two binary bits as input, but it also takes a carry-in.
01:56 It also has two output bits: sum and carry-out. A full adder can be built out of two half adders, and full adders can be wired together with the carry-out of one feeding into the carry-in of another to create as wide an adder as you like.
02:38 It’s a combination of an XOR and an AND gate. The dots on the lines indicate where the wires connect. If a wire crosses without a dot, that means they don’t connect. Lines A and B are the bits being added.
04:00 The full adder is built with two half adders and an OR gate. Remember that a full adder takes three bits: a carry-in plus the two bits being added. The sum of the first half adder is fed into the second half adder, while the carry-outs from the half adders are combined with an OR gate.
04:18 The full adder’s output is a sum bit and a carry-out bit. It’s adders all the way down, ladies and gents! Once you have a full adder, you can combine as many of them as you’d like into a cascaded circuit capable of adding as many bits as your heart desires.
04:37 The carry-out of each full adder is fed forward into the carry-in of the next one down the line. The first carry-in is hard-set to 0—there’s nothing to carry in—and corresponding bits in the number being added each get fed to a full adder. To keep the diagram clean, I’ve only shown a two-bit adder here.
04:57 The code I’ll show you in a second is a four-bit adder. It just keeps doing the cascade. In real circuit diagrams, the a bits and b bits are usually kept together so that the wires in the circuit correspond to the bits in a number being fed in.
05:11 That just means more crisscrossing wires in the diagram, though, so I’ve separated out the parts to keep the diagram simpler. You’ve seen how gates can be combined to form an adder. Gates are just bitwise operations, so now you can write a Python program that mimics this circuit.
The first bit of code to look at here is something that will help with the debugging. As this is for a four-bit adder, I want all my debug information printed as four bits. Recall that
bin() prints only the number of bits necessary, so I’ve written my own version of
bin() that always shows four bits.
Lines 7 through 9 loop through the bits of the value variable and peels them off one by one, sticking them in the
bit_string list. Because the peeling is from right to left, the bit list is backwards, with the least significant bit on the left-hand side.
It calculates the sum based on the XOR of the bits being added and the carry based on the AND combination. This is just like the circuit diagram. In both cases, I’m masking
1 to make sure to only pay attention to a single bit each. The resulting sum and carry values are then returned.
The input is three bits:
ci (carry-in). The carry-in and the first bit are combined using a half adder, resulting in a sum and carry. The carry from the first result and bit
b0 are combined using a half adder, giving the sum and a carry. And the two carries are OR-ed together.
09:25 And then print it out to the screen. Here I go. Let me scroll back. The result is a truth table for a full adder. If you’re too lazy to validate it yourself, go off to the Wikipedia page on adders. There’s a full adder truth table there. I’ve put the output in the same format so you can compare it visually.
The full adder can be combined a bunch of times to get an n-bit adder. I’m going to combine four of them. Lines 30 and 31 mask out
b to ensure that only four bits are being dealt with in either case. On line 36, a
for loop is used to grab each of the bit positions from both
Let me try it one more time with an example. On the third pass through this loop, for example, line 37 creates a mask by shifting
3. That is AND-ed in order to isolate just the third bit. As the full adder only ever deals with the least significant bit, the last step on line 37 takes the third bit and shifts it by three, making it the least significant bit. The same is then done for the
b bit on line 38.
And because this is only a four-bit adder,
1 is overflow, giving
0. Obviously, using a high-end processor to run a high-end language to do bitwise operations that emulate the gates that are used inside that very same processor is rather overkill.
Become a Member to join the conversation.