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:13 The next chunk is slightly more intense and it doesn’t do anything that you haven’t seen before in Python, but it combines a bunch of the ideas 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.

00:38 An earlier use of bitwise logic was in digital circuits, long before there was programming languages to work on top of them. Digital circuits are comprised of a series of gates.

00:49 Each gate performs a different bitwise operation. The rest of this lesson, we’ll be creating a four-bit adder. A four-bit adder takes two four-bit numbers and adds them together.

01:01 The logic here can be used for a bigger number, but it gets repetitive, so I’ll stick with just the four bits. A four-bit adder can be built with a series of smaller adders.

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:14 Don’t worry if all this hasn’t sunk in yet. I’ll show you some pretty pictures to help explain. Our circuit diagrams are going to use three kinds of bitwise operations.

02:24 These are represented as these three symbols for logic gates: AND, OR, and XOR. They correspond directly to the bitwise operators I’ve covered earlier. First, let’s build the half adder.

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.

02:53 The sum bit is calculated as A XOR B, and the carry bit is A AND B. Let’s add 0 and 0.

03:06 The sum is 0, and there’s no overflow, so the carry is 0. How about 1 and 0? The sum is 1, and there’s no overflow, so the carry is 0. And finally, two 1s.

03:26 In binary, 1 plus 1 is 10 (one zero). That means an overflow, so the desired carry-out is 1 and the desired sum bit should be 0. 1 XOR 1 is 0 for the sum. That’s good.

03:41 1 AND 1 is 1 for the carry-out. Look at that! The half adder is a circuit that adds bits. To make the next circuit diagram easier, let’s put all this in a box.

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.

05:30 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.

05:50 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.

06:07 Lines 12 and 13 turn the list into a string then reverse it. Finally, line 14 prints the result out. Let me import the method.

06:21 I’m going to loop from 0 to 10 hex. Remember that a single digit of hex is four bits, so that will print all four values.

06:32 In each loop iteration, I’ll call the debug print_unsigned() function.

06:39 Let me just scroll it back a bit here. And you can see, it is counting from zero all the way up

06:48 to 1111. So print_unsigned() works. Back in the top window, it’s time to look at the half adder. You’ll recall that it takes two bits as input. I’m calling them a0 and b0.

07:03 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 a0 and b0 with 1 to make sure to only pay attention to a single bit each. The resulting sum and carry values are then returned.

07:28 Let’s import this and test it out.

07:36 0 AND 0 is 0 carry 0,

07:42 1 AND 0 is 1 carry 0,

07:48 0 AND 1 is 1 carry 0, and 1 AND 1 is 0 carry 1. Good!

07:57 You’ve got a half adder. Back in the top window, time to look at the full adder. Just like the circuit diagram, this uses two half adders and an OR operation.

08:08 The input is three bits: a0, b0, and 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.

08:32 Let’s test the full adder out. Importing it.

08:38 Now I’m going to print a truth table containing all possible inputs for three bits. I’m going to do that by counting from zero to 1000 in binary.

08:53 I peel out the most significant bit from x and use that as a.

09:04 The second most is masked out and shifted as b,

09:10 and the third most is masked out and used as the carry-in.

09:19 These three bits are combined to get the sum and carry-out.

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.

09:48 Or, you can just take my word for it. It’s working. So, I’ve got some half adders, I’ve got a full adder. Time to do the four-bit adder. Let me just scroll the top window.

10:00 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 a and 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 a and b.

10:22 Lines 37 and 38 mask out the bit position and then shift it so that a bit and b bit both only contain the n-th bit shifted into the least significant position. That was complicated.

10:37 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 1 by 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.

11:09 The two bits in question are combined with a call to the full_adder() function, and then the resulting added bit is shifted into the s (sum) variable on line 41.

11:19 The cout variable is set so that it can be used in the next iteration of the loop. For debugging purposes, the print_unsigned() function is called and the sum is returned.

11:32 Let’s fire this puppy up. Importing the four-bit adder, starting with an easy case.

11:47 1 AND 0 is 1, that’s good.

11:54 3 AND 3 is 6, also good.

12:01 And because this is only a four-bit adder, 15 AND 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.

12:19 It’s kind of like having a nuclear-powered pencil. But sometimes, glowing in the dark is fun. As if all this bitwise stuff wasn’t complicated enough, I’ve got news for you.

12:32 There’s more than one way to combine bytes into larger things. Next up, endianness.