Logic gates

Here are some basic logic gates and how we can combine them to get an XOR:

In order to perform addition of arbitrary length binary numbers we first start with creating a Half Adder, which can add two single binary bits to result in a single two bit binary number. We can then create a Full Adder, which allows us to add three binary bits that results in a single two bit binary number. We need to add three bits as that allows to add two bits of two numbers and a carry bit. Next we chain together a sequence of full adders to add two binary numbers with any number of bits. We can optimise this to use bitwise operators to do ANDs, XORs and bitshifts to do the addition and carry operations on a sequence of bits. We can multiply numbers by doing repeated shift and add operations. Here are my whiteboard notes for all of these:

This entry was posted in programming and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.