XOR & the Half Adder - Computerphile
ฝัง
- เผยแพร่เมื่อ 5 ก.พ. 2025
- XOR, an essential logic operation, explained by Professor Brailsford. Continues our series on logic gates/operations.
AND OR NOT - Logic Gates Explained: • AND OR NOT - Logic Gat...
Binary Addition & Overflow: • Binary Addition & Over...
Capturing Digital Images (The Bayer Filter) : • Capturing Digital Imag...
Flip Flops, Latches & Memory Details: • Flip Flops, Latches & ...
The Virtual Reality Cave: • The Virtual Reality Ca...
XOR Easter Egg: • XOR Easter Egg - Compu...
The Professor's Notes: bit.ly/1BZARJI
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
"XOR and the Half Adders" is surely a good name for a band.
Darren Landrum but would the members play anything else than keys?
MAsYna Tutnga
Mi do nit czree
He is on
Dlaczego?
I spent 40 minutes of a lecture completely lost on this until my professor threw this video on "since he finished early" (he was lecturing at Mach 10, no wonder). Professor Brailsford is absolutely charming and explains things perfectly, with just enough fluff to hold interest but without veering off track. Thank you for the video, and I'm looking forward to binge-watching this channel in the near future.
@PIYUSH YADAV Someone doesn't understand hyperbole.
I am currently in the process of binge watching this channel.
1:35 Drawing the XOR gate in a logic diagram
2:30 Different names for an XOR gate
2:40 3-bit binary adder example
3:10 Example binary adder (without carrying)
3:45 Considering XOR with carry over
4:10 Drawing a logic diagram for a 1-bit part binary adder (or 'half adder')
5:05 How to generate the carry out bit
6:45 Full 1-bit adder
8:17 Overall truth table for all
8:53 Summary and round-up
This professor does an outstanding job of explaining. I used to program in 8080 and Z-80 assembly language and I learned a few things here myself. That's a very nice, clean way to do a half-adder.
6502 on my side, they chose EOR, a carry over from Motorola's 6800 instruction set when Chuck Peddle skunk-worked MOS Technology from them; same instruction though.
Good lord I love this man! Great energy and zeal.
I wish i had professors like Prof. Brailsford in my formative years.
This better explained in 9 minutes what a half adder is than my professor could explain in 60.
yep
gotta go fast
same
ikr, youtube has taught me more about for major than the teachers have at my uni for sure.
YES! I agree!!!
He came so close but I wish he would have explained that a 'full adder' is basically two half-adders plus an OR gate.
I could listen to this guy all day!
Same.
I can’t believe how Smart the guy is. How much is in that head.
yeah you could but obviously you're not :P
This guy is AWESOME, I love his explanations, and his demeanor all together great.
I just love this professor. After all these years, he is still so excited about computers.
bad memories came to my mind while watching this Video...
just 2 month before I build an 8 bit binary full adder only with BC547 transistors, 10 and 1k resistors as a school project.
I have to say: So many things can go wrong. It's just a pain in the back. especially when you only have 3 weeks and have to go to school.
but in the end it worked. Now I'm worried about my grade :DUpdate: got an A+ :DD
Fortunately I only had to build a 32bit ALU in verilog.
Derek Leung
Just got out of a 16 bit carry lookahead adder in VHDL
Heh, do "From nand to tetris" -that's fun. "Oh, just build a computer"...
Markus Mines I have done a small amount of transistor logic using 2N3904 transistors, but they are rated for slightly higher current (NPN, 250mA);also some 2N2222A transistors (NPN, 800mA);and MJE3055T (NPN, 8A);and IRF540N (N-MOSFET, 33A).usually, the smaller transistors are for signaling and logic, and bigger transistors are for driving loads (such as electric motors).a lot of it is mixed digital and analog electronics, with parts operating at different voltages (3.3v, 5v, 12v, and sometimes higher, ex, 15v-24v).transistor logic isn't really fun, much easier to do any non-trivial
logic using microcontrollers or a Raspberry Pi or similar... (leaving the discrete electronics mostly to non-logic tasks).wouldn't look forward to building complex digital circuits with transistors.most complex I built was a circuit for running bipolar stepper motors with transistors (sadly/ironically, thus far works better than my attempts at using driver ICs).NPNs are good for small digital circuits, and have good properties for analog, but the drawback of generating considerable amounts of heat. a few of my NPN-based circuits (simple analog logic) are actually insulated with silicone caulk and run while submerged in water for this reason, and may actually cause the water to start boiling off the transistors while running (yes, actually built the thing to run underwater...).MOSFETs, however, are more expensive and don't deal as well with analog signals (in a simple sense, they like to behave more like on/off switches).well, and of course, a lot of this stuff is wire-wrap (typically with 24 gauge wire, or thicker for higher loads), and a lot of resistors, capacitors, and a few ICs and other things in the mix as well...but, it is worthwhile I guess...
+Brendan Bohannon The npn transistors you use for digital logic that give off heat, are you using resistors for that? It shouldn't overheat like that for simple digital logic.
Every video with Prof. Brailsford in it gets an instant thumbs up from me :)
I remember learning about XOR in electronics and graphics when I was a kiddie. I thought it was SO amazing. Drawing moire-patterns and trying to make a full adder... oh happy days.
This guy is the best. Putting in my application for Grandson right now.
Taking a class where we have to build these and test them on a circuit. Very helpful video. Thank you!
I think it will be a great followup to this series if it is explained why a four bit adder is more efficient than adding up four full adders and what is the most efficient adder.
Computerphile makes my brain happy.
I've implemented a 8bits full-adder in Minecraft, that helped me A LOT ! :)
I did a 24 bit full - adder, why 24? Because it got real boring after 23... ;)
hmmm, without mod, I doubt, you would have been out of chunk loaded area :)
Ya, you're probably right, must have been half-adders, I don't remember, my bad (Still got boring after 24):)
XD
kanethornwyrd On second thought, I think I got a full adder to work in like 9x5 blocks or something. But I might be mistaken ;)
I've started working with assembly about a month ago. Learned to love the xor operation.
swap 2 registers? xor that shit.
set a register to 0? xor that shit.
modulo(2^n)? xor that shit!
Also if you look at the table for the fulladder you can actually read it as binary number.
bin:1 1 1 = 11
dec:1+1+1 = 3
bin:1 0 1 = 10
dec:1+0+1 = 2
So you can very easily see that the circuit is in fact a fulladder :)
I just wanted to thank you for taking the time to do this. I really appreciate this video.
This guy is such an amazing teacher
I never been so excited about a Half Binary Adder :)
Perfectly constructed video, well done Prof!
For over a year I have been playing a video game with logic gates in it and I made a bunch of simple games like tic tac toe and dots and boxes but I could never figure out how to make a calculator and now just looking at videos for fun I see this explaining how to do simple addition with logic gates.
Wait a minute. I'm out of redstone.
Lol
ÀAAaaàÀà@@asaffisher8890
i have like two stacks of torches though...
Such a nice way of presenting these logical operations. Unfortunately, at least for me, in school ,they didn't get presented as nice, felt a bit more complicated than it really is and less interesting.
this video changed my life
8:25
cin تعني ما أحمله باليد واحد
a,b حاصل جمع عددين عاديين فإذا كان صفر أضف ما كان لديك في اليد واحد (cin) إلى الأحاد كما في الحالة الثانية
إذا كان
a+b=2 اي 10 في النظام العشري قم بحملها في الcout الحالة قبل النهائية
I'm not even religious but GOD BLESS THIS GUY!!!! He is so amazing.
My jaw dropped when he did the addition. I can't believe that works
I've thought of a way to make a half adder using only 3 gates. A xor gate is made from a or gate with the inputs tied to a Nand gate controlling the output. If you replace the carry out with a signal from the and gate before it is inverted. I have tested this shortcut in Minecraft with success.
I know it's 5 years later, but the problem with this idea is that an or gate in itself is 4 nand gates(you need to invert both inputs and output) or 2 nor gates(invert the output). There is no way to electronically do an or gate directly. So while you are correct in a sense that an half-adder can be done in three operations, unfortunately one of those operations requires 4 gates to do.
TL;DR
Yes, as long as you ignore the fact that the OR gate is actually 4 NAND gates, since we can't make an OR gate directly, unlike a NAND or NOR gate.
Yes; we all knew immediately and without thinking about it all that binary 101 is 5, because only awesome people like us watch this channel!
we did? of course we did!
.>
Wow, this is an amazing description of the half adder. Really enjoyed this video!
so helpful, best explanation ever- really going to help with my exams :))
If you want to know the 'equivalency' gate, its XNOR. XOR with a NOT(inverter) tacked on. It returns a 1 if both inputs are the same.
this video is a gem 💎
I'm surprised there was no mention that XOR on {0, 1} forms an abelian group. It is the only logical operation that has such a nice structure afaik
Excellent video for basic logic gates.
Fantastic communicator and teacher -- thank you
I've often seen XOR notation use the '^' symbol, e.g. A ^ B. I'm surprised that one was left out. It's very common in programming languages.
@Connor Gaughan Actually, that’s (A∨B)∧¬(A∧B). ∧ and ^ are different symbols.
Nice. Now blow everyone's minds with the SR and type D latches.
Brilliant teacher
i was bored so a coded a little binary converter, thanks for the easter egg
A full adder can be done as follows: first bit: xor them & and them together, carry the and gate result to the next bit. All other bits: is there a carry bit? If so, xnor them together and or them together. Carry the or result. Otherwise, repeat the first bit process.
Brings back the memories of hours spend on redstone machinery
I built an 8 bit adder on my own PCB once, so satisfying
Konrad Zuse realized his first (mechanical!) computer Z1 in 1938 which could add and subtract numbers. Not just integer numbers, but also floating point numbers. The machine consists of 30.000 parts. It was the first working computer having input, output, memory and a central processing unit.
yess!!!! my favorite topic logic gate how the magic works!!!! i subscribed because of this video! and liked!
Isn't it easier to think of the circuit as two half adders with the carry outputs OR-ed together ? Provided you convince yourself that it is impossible for both half adders to produce a carry, I think this gives more insight.
beautiful beautiful video understood straight away
It's 4:30am, I'm tired as hell, and this still made sense. There's something wrong with me.
thanks, you are such a great proffesor
I love the video thumbnail with the half snake (indeed a half adder) :D :D
This is a fantastic video
This makes it easy to do subtraction with 2's complement: Invert the bits for B and carry in a 1.
Loved this video!! Loved Loved LOVED this video. ❤️👍🏻😁
this guy is great.
I like to think of the xor giving an output if the number of inputs on is odd and it doesn't give an output if the number of inputs on is even. That way it works for if you have a lot of inputs into a single xor gate.
You explained that so elegantly, I couldn't of explained it that well
I know all this things but still I hear this things as a story , when professor explains...
One important thing that you forgot to talk about is that XOR is not just a way to have output 1 only if you have 1 input signal. In fact, if we have 6 input XOR gate, 1 on the output will apprear only, when the sum of input signals is not even. For example: 1 signal on input gives us 1 on output, but if we apply 3 signals on input, it still gives us 1 on the output. 5 signals on the input - still 1 on the output. 0,2,4,6 - even numbers - so there is no signal on the output.
I'm pretty sure they stuck to two inputs for simplicity, and because it ties into their earlier logic addition content. Besides, a 6 input XOR is just five regular two input XOR gates stuck together. You start by putting three pairs through, and getting three outputs. You put outputs 1 and 2 through another XOR, and then take that result, along with you third output through the last XOR. I'm sure there is a smarter (at least less transistor heavy) way to do it, but you don't need dedicated 6 input XOR gates, just like you don't need more than two inputs on any other logic gate. AND and OR gates combine into their respective 6 input versions the same way as XOR.
Improbabilities You are certainly right.
Thanks sir ❤️
Love this guy.
Will or did you guys do a video on Karnaugh maps?
I wonder if the professor is going to cover methods to derive these expressions from truth tables. That might help the layman understand why the full adder looks the way it does and how to derive the gate sequence without memorizing it.
You can do it out of the truth table. Try to draw it on a paper. Start with the half adder. Then try it like this: if a & b are 1, and the carrier is 1, output should be 0 and carrier 1 etc... write this down and try to figure out how to place the and, or & xor gates, it'll work.
Merthalophor I know how to do it myself. I'm just curious if they are going to cover Boolean Algebra, K-maps, etc. For instance, every time you have an output that equals 1, add a term to your OR expression that guarantees only that combination of inputs equal 1.
Your regular output would be
(~A^~B^C)v(~A^B^~C)v(A^~B^~C)v(A^B^C)
Which eventually can be converted to
(A XOR B) XOR C
Your carry output would be
(~A^B^C)v(A^~B^C)v(A^B^~C)v(A^B^C)
Which eventually can be converted to
((A XOR B)^C)v(A^B)
or
(A^B)v(B^C)v(AvC)
iabervon I wouldn't say never. You can always get to the triple-input XOR, and I think it is important to learn how. Also, I'm more concerned with the average viewer trying to figure out the Cout expression on their own, which can help teach them how to figure any expression on their own.
KrunchyGoodness I'm hoping there will be a Karnaugh map video at some point. I think they make most sense when talking about something like instruction decoding, where you've got a really arbitrary truth table you have to implement, rather than one with structure you can reason about, so I'm fine with saving it for later. Also, it's worth talking about glitches first, because avoiding glitches is an important use of Karnaugh maps.
The title should include the Full Adder as well since it was mentioned as well ;-)
Also explaining the peculiar way that multiplication is done in a computer will be fascinating.
I really wish you were teaching my courses!
The OR gate before C(out) could be an XOR as well, because both inputs can never be one, since for the bottom wire to be on I this diagram, A AND B has to be on, and for the top wire, C(in) and the output of A XOR B has to be on, but A XOR B will not be on since A AND B was on. So you only need two types of logic gates for this!
Absolutely fantastic! Thank-you for sharing! :)
what a pleasure a presentation with a UK accent to avoid the littering of rouloulou accent from India!
I love this professor :D
What is the purpose of the "carry in" shown at the end? How does it exactly fit into a mathematical expression?
I think a carry in, is if you carry 1 but in he number, so you have to add it to the next column wich already exists. But i'm not sure.
Gotta love the 1980s printer paper pad
Lol, speaking of binary adders I managed to make a 4 bit binary adder in Minecraft without knowing any logical operations other than AND and OR... I literally just brute forced it for like 10 hours and found a design that was highly impractical but worked, and then I found out that the inputs were the wrong way round and it was carrying the wrong way round too XD so I had to rewire a load of stuff.
Gg
tl;dr:
a⊕b = (a+b)&¬(a&b)
and
a⊕b = (a&¬b)+(b&¬a)
you can actually construct xor from and and or by starting with an approximation and refining it.
I can start with approximating a⊕b with a+b. this gets 3 out of four correct.
I can then look at what the incorrect one should be(0) and what conditions make that case(a=b=1)
I can take the result of my first approximation and and it with 0 to force it to be zero, but I only want this to happen for this fourth case.
so now I have a⊕b as (a+b)&c where c is zero if and only if a=b=1. sounds a lot like not and, doesn't it?
then we have a⊕b = (a+b)&¬(a&b)
another way to construct boolean functions for any arbitrary truth table is to find all of the cases where the result is one, create an expression that is only true under those circumstances, and or those expressions together. that ends up with a⊕b=(a&¬b)+(b&¬a)
faissialoo well here's a XOR in Boolean. A⊕B = (A∨B) ∧ ¬(A∧B).But if you're gonna make a XOR in Minecraft I'd prefer (A ∧ ¬B) ∨ (¬A ∧ B) as it's simpler to understand.The second one is easier to follow in my opinion. ∨ = OR ∧=AND ¬=NOT ⊕=XOR
Merthalophor every logical function is derived from OR and NOT. All computational can be done with just those two and all other gates are derivations of them.
Nickster258 Both work. You're _wrong_. "All other gates *can be devirated from them".
it is interesting that, if you have a xor gate it is synonymous with a 1 bit quarter adder, in the same way that if you have 1 proton particle it is synonymous with a atom hydrogen
Best easter egg ever :D
This dude is hardcore!
My only complaint is HE ALWAYS GETS HIS HANDS IN THE WAY WHEN I TRY TO PAUSE TO SEE THE SCHEMATIC lol
wishcraft4u2 LOL I had to pause the truth table a few times to make sure I understood it all too. He's an excellent teacher!
hehe i can get it if i watch for like 2 to 4 times
Blame camera's pos
Super hardcore? We made this full adder the first semester of computer science at Uni. First on paper, then implemented it on a circuit board. Granted, it wasn't a walk in the park.
Thank you so much !!!!
Is Bill Gates a logic gate?
Yeah, whatever input goes through it always comes out much larger.
lol
a set of gateS; And, Or, Xor, Not, Nand, & Nor.
And gate , Or gate, Nor gate, nand gate,.........,bill gate 😂
😂😂😂
7:16 "easter egg"?
I already guessed what 7:18 says.
( I translated it afterwards and jup. I was right!)
Why the last stage of carry out is an OR and not a XOR? It can't have two 1 at the same time as input
can you show me the circuit of a full adder attached to an output and an input
How do you do an Xor on two whole numbers or base 10 numbers?
do n=np problem :)
If anyone found this at all unclear, I urge you to go watch the Numberphile video titled "Domino addition". It shows this exact thing using dominoes and is even simpler.
Thank God there are smart people in this world who come up with this stuff. We dumb people would be living in caves if were left up to us.
So how do you use it in a situation where you can't carry a bit?
demasiado claro!!
With all these parallel inputs needed, is there a gate that takes one input and generates two outputs? It seems all of these gates decrease the number of signals, what does the reverse?
Gareth Dean Multiplexers. Binary number on input defines which of output wires is active. Of course that consists of applying technically separate logical function on inputs for each output wire.
kasuha
Cool, thanks.
kasuha What you described is a Decoder. A Multiplexer has one Data input, n select inputs and 2^n outputs. The binary number on the select input defines which output the input signal is forwarded to.
swiss It's a while since I stopped having fun with designing hardware circuits, I'd swear we used to call these parts that but apparently I was wrong. It's even a demultiplexer actually. I'd guess we were just lazy to use such a long name for a part we were using all so often.
What is carry? what does it used for?
feels good that I figured this out myself in minecraft
I remember building that in Minecraft "Redstone logic"...
Can someone give me the link to the concept of carrying, if they did a video on it. Or an external link perhaps. Or just a brief run down. Thanks.
Could the third OR gate be an XOR as well?
One thing that always kind of irks me is that people usually show the diagram... and then the table.
When, in most cases, you model your diagram after that table.
It's like showing a house, giving me a full tour, then showing me the blueprints to assure me the outlets actually work.
Let me put it like this: The table is the 'what it needs to do' and the diagram the 'how do you do it'. I don't know how you're doing what if I don't know what it needs to do.
I love this man!