How can we use logical operations?
Contents
20. How can we use logical operations?¶
20.1. Admin¶
20.1.1. Grading Contract Updates¶
You can reduce your more practice days completed by 2.
You can reduce the number of deeper exploration by 1.
Important
Review your grading contract and either submit that PR, or an issue noting if you need another update.
20.1.2. Deadlines¶
Things submitted by May 5 you can revise again.
I will hold office hours for your last chance to do final touches during our exam time May 10, 11:30-1:30.
I will do final grading starting May 11 in the afternoon; all work must be submitted by noon May 11 to guarantee grading.
I will post additional office hours and feedback hours during finals week soon.
21. Why do we need to think about bitwise operations?¶
Understanding them is prereq to what we will see today and that will help you understand hardware overall.
You of course will not need every single thing we teach you in every single class.
Seeing topics once at least is the only way you can make an informed decision to study a topic deeper or not.
Seeing a topic in more detail than you will use all the time actually helps you build intuition, or deep understanding, of the topic overall, and help you remember what you need to remember
21.1. Bitwise operators¶
& : and
| : or
^ : xor
~ : not
: shift right
<<: shift left
Let’s review truth tables for and, or, and xor.
a |
b |
output |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
a |
b |
output |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
a |
b |
output |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
In order to implement more complex calculations, using gates, we can use these tables as building blocks compared to the required output.
There are more gate operations; you can see a simulation for 16 gates
21.2. Adding with gates¶
Let’s review adding binary numbers
add the two bits
carry the next place like in adding multi-digit numbers otherwise
We first add the ones place and get a 1, then the two’s place and get a zero then the 4’s place and get 0 with a carried one.
In this case in the ones place we add 0 + 1 to get one, the two ones add to 0 with carry then 1 + 0 + 0 gives another 1.
let’s make a truth table for adding two bits.
a |
b |
out 2’s |
out 1’s |
|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
Now, what gate can we use to get the output 1’s place bit and what gate can we use to get the output 2’s place bit by comparing to the truth tables above.
It turns out the one’s place is an xor gate, and the two’s place is an and gate.
This makes up the half adder, try one out at this simulator.
So this lets us as two bits, but what about adding a number with more bits?
We can put multiple together, but there’s one more wrinkle: the carry.
That’s what makes a full adder different. It adds three single bits, or a carry and two bits and outputs the result as a sum bit and a carry bit.
Then we can link many of those together to get an 8 bit ripple adder.
Alternatively, we can “lookahead” with the carry bit, passing it forward multiple places all at once, as shown in this 4 bit carry lookahead adder.
21.3. How can we choose between things?¶
A mux (multiplexer) is a component (like a gate is a component) that allows us to select one operation out of a circuit.
21.4. Prepare for next class¶
Compare the 2 bit multiplier to the full adder in
multiplication.md. Use that to explain how it works, relative to the fact that multiplication can be thought of like repeated addition.Study the 8 bit ALU. Try it out and be prepared to answer questions about how it works on Thursday.
21.5. More Practice¶
In
addertypes.mdcompare ripple adders and lookahead adders.1. Give a synopsis of each adder type 1. Compare them in terms of time (assume that each gate requires one unite of time) 1. Compare them in terms of space/cost by counting the total number of gates required.
(priority) While we saw many types of gates today, but we actually could get all of the operations needed using only NAND gates. Work out how to use NAND gates to implement a half adder.