Binary Addition & Overflow - Computerphile

Back to basics, at the start of a series on binary numbers Professor Brailsford tackles binary addition and just what is meant by an overflow.
How Gangnam Style Broke KZbin: • How Gangnam Style Brok...
Public Key Cryptography: • Public Key Cryptograph...
Where's the Money in Free Software?: • Where's the Money in F...
Blogging Guitar: • Blogging Guitar - Comp...
How Signed Binary Works: Coming Soon - Subscribe for Updates
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com

[@profdaveb6384]

Presenter is FIRST. YeeeeeeHah!!!!

[@detaart]

LOL

[@miroslavhoudek7085]

No fair - it was easy for you to ... carry out.

[@jcasaubon]

haha.. When are we going to see two's complement?

[@BradenBest]

***** You _could_ just read my comment from 2 years ago. I gave a detailed explanation of two's complement (the standard implementation of signed numbers), while simultaneously not understanding what one's complement is. One's complement is ~n Two's complement is ~n + 1 I.e. in a 4-bit system, 1111 (F or 15 unsigned) is 0 (~1111 => 0000) if one's complement (extremely rare), and -1 (~1111 => 0000 + 1 => 0001) if two's complement (nearly every platform uses this convention). You know a number is negative if its sign bit is on. The sign bit is the highest-order (leftmost) bit. The whole 1's vs 2's complement is the reason why in C, you are only guaranteed a range of {-32767 .. +32767} instead of the expected {-32768 .. +32767} for the `int` type (which is guaranteed to be >= 16-bit), because C reserves one's complement for portability to one's complement systems.

[@GKinWor]

@@BradenBest :/

[@piggiesgosqueal8066]

Explains topics like no other. Makes it easy to understand. I've watched several of his videos and they all have helped me significantly.

[@freddiebird1623]

Ahh, the David Attenborough of the computer world.

[@MorrisTart]

I had a lightbulb moment a few years ago when I realised that DNA (and RNA) use a base 4 numerical system since there are 1 of 4 nucleic acids, A T G C, in each position of the strand. When coding for proteins, these are grouped into blocks of 3 to encode one of the amino acid units that make up proteins and biologists call those blocks Codons. In computer terms it's just like a Byte, where DNA has 3 digits in base 4 instead of the digital computer's 8 binary digits.

[@Jossyish]

Amazing! I wonder how you would do operations.

[@resonance2001]

Your voice and manner is well suited for teachning. If only you were my teacher when I was at college...

[@MarkIsJustKidding]

Phenomenal Clarity! Best Binary addition video on youtube. Thanks so much

[@strangersound]

This was very helpful, especially when understanding base number systems. A little bit of time and scratching with my pen, pad, and calculator, I was converting binary, hex, and octal values. Thanks for that. The trouble started when I made up a couple of binary values to add and then convert them to check my answer, but I inadvertently did an overflow situation making up random binary strings. So I did some searching to try and understand how you can add two binary values in 8bit that would equal more than 255. That lead to explanations of bytes, words, registers, etc; and Two's complement, and signed vs unsigned binary values; bit shifts and integers; aka: a lot more to read and understand. The more you know, the less you know. ;) But the logic gates playlist and this video were very helpful. Numberphile, Computerphile, etc may not be a full education on these subjects (that's up to the individual to follow up), but they do serve as an excellent primer to introduce these subjects and make them fun which helps generate the interest and desire to learn more. Thanks again for all these great videos. :)

[@AlbySilly]

FINALLY! This series will be very useful for me and will save me a lot of headache. Thank you.

[@MrRenetho]

yaaaaaa, we've run out of space :D

[@oafkad]

ProfDaveB Kinda bummed you were never my professor. This video was amazing. I went from not getting buffer overflow in any reasonable sense to getting it in a matter of minutes... And jeeze...I can count in binary now O.o...

[@StajahLeeHoeflich1314]

How could 37 ppl (at the time of my viewing) not like this video?! This Professor Brailsford is awesome! I'm in intro to Comp Engineering and reviewing this using this video is so great.

[@Kryoclasm]

I only wish you could have taught my computer classes. i don't know how you do it, but you just seem to make these concepts solidify in record time.

[@RoelfvanderMerwe]

This guy is awesome. I wish I could have a teacher like him

[@saketsahu7877]

sir plz post for advance topics, you explained very clearly

[@michaelnajera7958]

I wish all of my professors were this cool!

[@Ratstail91]

Ok, so when you're actually implementing this on the hardware level, the granular logic applied to each column (carry in, add, carry out, repeat) is repeated for each bit in a number. Is it easier/more common to install the logic circuit once for each byte, or to run each byte through the same logic circuit?

[@thefauvel7558]

This guy is awesome!

[@MrGeekGamer]

"Back to basics" Hurrah!

[@AgEyal]

This guy has to do some narrating in Video games!

[@johndingo4633]

Thanks! it's good to step back a bit sometimes

[@SparkysBarelyMusic]

The lighting is really nice and warm in this one, have you installed a fireplace in your office?

[@WichidNixin]

This video really gets intense at 4:30

[@Skiwai]

even more intense at 6:15

[@rcedwards]

@@Skiwai Had to dig into the comments to find this.

[@PhilBoswell]

I am not the only one to observe that 0⁰ is not 1, but then base-zero arithmetic is only for those theoreticians who like giving themselves and their readers raging headaches :-P

[@messyzephyr]

Simon WoodburyForget Unless you're actually doing math.

[@coopergates9680]

Phil Boswell Base zero can only represent zero yeap

[@Wargon2013]

To say 1111+0001 is a overflow kinda confuses me because I learned that the "overflow flag" is totally different than the "carry flag". For example: 0111 + 0111 = 1110. Unsigned its 7 + 7 = 14 but if I'm using two's complement its 7 + 7 = -2 and because it doesn't make sense that a addition of two positive numbers results in a negative number I get a "overflow flag" but I don't get a "carry flag" because 14 can be stored within 4 bits. 1111 + 0001 = 0000. Unsigned ts 15 + 1 = 0 plus a "carry flag" because 16 can't be stored within 4 bits but if I'm using two's complement its -1 + 1 = 0 and that is absolutely correct so I don't get a "overflow flag"

[@grivar]

+Wargon You are correct. As everything he did in the video is unsigned, there cannot be a overflow. What he should have said is that it is a carry.

[@breadbaconcheese]

+Wargon I was learning about asm too and noticed this to be quite confusing. My understanding on Overflow flag, it's used when working with signed number e.g. -128 to +127. Calculating 65+65 in 8bit signed number will cause overflow flag to be set because +130 is outside +127 range. IMO, the video is talking about a carry out, not overflow?

[@Wargon2013]

breadbaconcheese Yes, I also think he is talking about carry out. Imo it kinda makes more sense to say an integer overflows when the numbers get too big like a glass overflows when you try putting too much water in it (so I was quite confused when learning it for the first time as well^^). ...but I have no idea why the one thing is called carry and the other one overflow. Both don't really tell you what is going on (Sign-Flag and Zero-Flag have much better names)

[@leandrog2785]

carry out is overflow

[@Madsy9]

I just wanted to add a small detail to Professor Brailsford's explanation of arithmetic overflow. Whether or not "1111 + 1" overflows depends on the number representation used. If the number is unsigned, then it obviously overflows because "1111" represents 15 in decimal and there isn't room to represent 16. But if the number is signed two's complement, then "1111" represents -1 and adding 1 naturally gives zero. That's what should happen and is not an error in that case. In computers, the arithmetic unit in the CPU have binary flags which indicate whether a signed overflow or unsigned overflow happened during the last instruction. Unsigned overflow is indicated by checking the carry flag, and signed overflow is indicated by checking the overflow flag. The signed overflow flag is set whenever the most significant bit in the result from the operation is set. For example if you add 1 to the byte 01111111. 127 in decimal is the greatest value a signed 8-bit byte can represent, and adding one to it will wrap around to -128 (10000000).

[@linkVIII]

Had class about this just yesterday in comp org

[@rillloudmother]

I must say that Professor Brailsford has a very soothing voice and manner of speaking. He quite reminds me of the great Sir David Attenborough.

[@joeder2]

You're great guys

[@PeterWalkerHP16c]

This is where playing with an HP-16C programmers calculator is really useful. After a while carry flags, overflow flags, complimenting, rotates, stacks and operators become second nature. Perhaps not much use with Javascript, but boy, if you're working with word logic, state machines and ALUs etc, it's your world view.

[@Kiwipai]

Anything to the power of 0 is 1? But in numberphile you guys said that wasn't really true for 0^0

[@hikari_no_yume]

It's not a problem when dealing with bases, there's no base 0, and base 1 isn't a positional number system.

[@TheMajorpickle01]

(x^a)(x^b) = x^(a+b). Therefore (x^a)(x^0) = (x^(a+0)) = x^a therefore x^0 = 1 as for 0^0, it's dependant on the system

[@AssistantJames]

I like how numberphile has brown paper so computerphile has ol computer paper. Nice touch.

[@OSEA81]

Thank you, sir; you've saved me a headache

[@commanderlake7997]

To increment binary just look through the bits from right to left and change the first 0 you find to 1 and set all the 1's to the right of it to 0.

[@FatihErdemKzlkaya]

hey, it would be amazing, if you had done a video about how binary files work

[@fe4000]

Photographer learning digital image processing in Python here. Yes, overflows can definitely occur.

[@VandalIO]

Do a video on LNS logarithmic number system and European logarithmic microprocessor (ELMS) please

[@matbroomfield]

So what if you were adding not just two columns, but hundreds, and the units column contained a 1 in every single case? Do you have to divide the total number to find all the binary columns that 1s must be carried too? If so, that seems extraordinarily cumbersome, and is a totally different way of operating than decimal.

[@leandrog2785]

Try adding 999999999999999999999999999999999999999999999999999999 to 999999999999999999999999999999999999999999999999999999 in decimal. It works the same way as binary

[@SirFancy]

Can you do a video on Two's Compliment?

[@onixtv4034]

Which is better numberphile or computerphile?

[@MaipuruSyrup]

I would have liked to know more about the implications of an overflow.

[@LiyaxD]

Its a bit more complicated than F+1 for the reason that KZbin`s engineers use signed integers witch means that the integer didn't overflow but rather got into the negatives. The 32nd bit represents the sign bit and the following 31 bits represent a binary number as in two`s complement system. So you could say that the 07ffffffffffffffffffffffffffffff+1 overflowed into the largest negative number in 32 bit representation.

[@Jelle_NL]

1:17, except 0 itself.

[@brooped]

10:17 on a 7-minute long video?

[@Astralify]

brooped overflow lol :D

[@JGrffn]

pretty sure 0^0 = 1

[@Moshikashitenai]

Joseph Griffin I'm pretty sure it's not. Break 0^0 down, and you'll get a division by zero, because multiplication is just division in reverse. 2*2 = 2² 2²/2 = 2*2/2 = 2 = 2¹ Repeat this pattern with the output you just got, and you end up with this: 2¹ = 2 2/2 = 2^(1-1) = 2^0 = 1 Exponentiation is multiplication, so 0² would be 0*0, so apply the above pattern to that. 0² = 0*0 0¹ = 0*0/0 0^0 = 0/0 = undefined

[@JGrffn]

Moshikashitenai so every calculator in the world is wrong? Even C++'s Stl pow()? The explanation as to why you're wrong and why 0^0 =1 is actually quite long, too long to even bother to try and type through the phone, so I trust you'll be able to look up the answer for yourself. Just remember, "I can do all things in Google who strengthens me."

[@seanearnest]

1:42 Thought I had a vertigo attack. Great video though!

[@GhostyOcean]

But how do you do higher level things like multiply or use exponents?

[@buggyland]

Without a hardware multiply function you execute a loop of additions eg: 5 x 3 is 3 loops of +5 etc.

[@mikecimerian6913]

The beauty of binary. To be or not to be. All other bases leave me null.

[@bouguezinemohamed767]

No one : Computerphile : 6:15

[@matthewmorrison2071]

How would a computer deal with crazy over flow such as [2^16]*[2^16] with a 16 bit computer

[@5H4D0W_60D]

Most computers break up and store the product of bitwise multiplication into two registers, if I'm not mistaken. The computer will store the first 16 bits in one register and the remaining 16 bits in another register in your example. The product of two n-bit values will never exceed 2n number of bits, e.g., a 16-bit value times another 16-bit value will never produce a product with more than 32 bits.

[@thepumpkingking8339]

With overflow. Why do I have the mental impression of a guy in Burberry coming out of an off-licence with one to many can's of Frosty Jack in his bag and being stopped by the Buffer Police.

[@piguy314159]

If I want to tell a computer to add 314 + 159, I don't have to type 100111010 + 010011111; I can enter the numbers in decimal, and it will print out the right answer in decimal. So computers must understand decimal, too; how do they switch from decimal to binary and back?

[@calrogman]

When we say that computers don't understand decimal, what we really mean is that they can't WORK with human readable strings of numbers. Those aren't real numbers, just a representation. Before we can do anything with them, they have to be translated into a machine readable form. It happens that the characters 0-9 are sequential in ASCII, so if you're using ASCII, this is actually pretty easy. You initialise a variable to 0, then, for each "number" you see in a given string, you multiply the variable by 10 and add the number, minus the integer representation of 0. Here's an example of a (naive) C function that takes a string containing an unsigned decimal number and return an unsigned integer. unsigned int readnum(const char *s) { unsigned int r = 0; for(; isdigit(*s); s++) r = r * 10 + *s - '0'; return (r); } The inverse operation, giving the decimal representation of an integer, is left as an exercise.

[@lamaranadiallo9790]

Life savor

[@Tyranisaur]

I can sense 2's compliment coming up next.

[@MrZiron94]

Validifyed "No one" except every computer in the world...

[@MAlgMAlg1]

Henrik Rostedt no, I know exactly what I meant. I simply tried to imply that there may be a video about the sign-absolute way coming up first.

[@HenrikRostedt]

MAlgMAlg1 That comment was directed at +Validifyed. There is nothing wrong with your prediction.

[@MAlgMAlg1]

haha, ok :) I replied to that in a rush :P

[@locust76]

It's worth noting that a carry-over in decimal is no big deal, just add one column to the left side of the result. The problem with binary is that the number of columns you can have is pre-defined by the machine. A 32-bit machine can only work with 32 bits. a 33rd bit causes an overflow and will be dropped, because there is no physical or logical room for it.

[@buggyland]

Dropped? umm no it won't. CPU's (ALU's) have a special bit register for exactly this problem called... CARRY. If the carry bit is set you had a CARRY in your executed operation. This fact should have been included in the explanation for completeness.

[@EwanMarshall]

2,147,483,647 is limit of 31 bits, not 32 (one is already used for +- sign), and one could carry into another variable. Look at the highest number python will handle (hint how much RAM do you have, as it will keep switching data type and pulling all sorts of these tricks to store and perform arithmetic on any number it physically can).

[@randomjasmicisrandom]

Because Michael Gove binned ICT in British Secondary Schools (just stating a fact, not trying to get into politics!) I now teach 'Computing'. I have tried to teach this very thing in exactly the same way to 12 to 13 year old's. The sound of howls of pain, confusion, heads blowing up and screams of protest were heard the other side of the school.

[@randomjasmicisrandom]

Weird fact, they hated the theory of what was going on, but loved learning to count in binary on their fingers. Especially when they got to demonstrate the numbers 4, 6, 128 or 132 to another teacher. (There was one other absolute favourite number they got to demonstrate, can you work it out?)

[@tommythai1043]

randomjasmic 384? 390? And I wasn't aware ICT was removed from the syllabus... Just left compulsory education recently and we all did ICT, not this stuff though. We'd only did this in maths or our spare time (given we had an interest). Or if you decided to do computer science at uni in which case this contributes to an easy first year.

[@randomjasmicisrandom]

Removed altogether in favour of 'Computing'. While I don't deny some aspects of programming and computational thinking needed to be included in the curriculum to get rid of the entire ICT syllabus was a knee jerk reaction. You can still teach ICT if you want to, but computing is compulsory. And yes, 390. Oh, how the little darlings loved that number!

[@minasalah2668]

5:00 you said 2+1=3 so we gonna write 1 and carry the 2 but you wrote 1 and said 0+1=1 why is that ?

[@eisforellabean]

because the original 1+1 would be 0 but then you're carrying in a 1 from before so 0+1=1 in the column. hope this helps!

[@inphuriated]

have to have a listen to gangnam style thanks to this..

[@j.1985]

Hello Suffolk one class!

[@PauloConstantino167]

What nobody notices when they say that the Nth numerical position is really 10^N, is that this is a redundancy. You are trying to define 10^N by using 10^N. See it? There's no way around it though, but it's funny.

[@freedom3229]

How do you add 1 to 1111?

[@MrFollowboy]

make a 16 bit 0001 0000

[@DaveLillethun]

I was going to suggest doing two's complement next... Then I saw the "Coming Soon". Read my mind, apparently! :)

[@DaveLillethun]

PS - Just a note: This video shows overflowing an unsigned number, and the Psy video is talking about overflowing signed numbers. It's slightly different, but I suppose we'll see in the soon-to-be-released video about negative numbers.

[@AndreAmorim-AA]

Reminds me ip subnets calc ;)

[@CYXXYC]

Press 3 and 6...

[@AnstonMusic]

Aerden Mitalrythin I don't?

[@CYXXYC]

Andy Flow [Music Producer] press 3 for word "3" and 6 for "+1=2"

[@AnstonMusic]

BurnyCreative Huh? It doesn't cut like that for me. I can hear the second sentence from the beginning, "1+1=2" , and so I though you just pointed out how ridiculously obvious things were said out loud.

[@FeLiNe418]

how do you discover these things? LOL

[@themanwiththepan]

3, 6, and 7.

[@hygkolk]

thats a satisfying pen :P

[@CYXXYC]

first besides computerphile

[@GegoXaren]

Err... the problem with the YT overflow was that they used signed ints and not unsigned. Why in balls name would use signed integers when there can not be negative views?

[@bergweg]

I thought you're going to mention the Ariane 5 explosion

[@austinhruska7473]

I hate how everyone who is describing binary puts a cap on the length. people who are new to binary usually have never encountered the concept of a number system that inst in base 10. I think it should be thought and formatted in the same way we would count(1, 10, 11, 100, 101, 110 etc) and then introduce the idea of counting from 0, limiting the number of digits, and the short cuts.

[@patrickford9615]

"ANYTHING to the power 0 is 1." Careful there. 0^0=/=1. Zero to the power zero is indeterminate! Gotcha. (Now I gotta restart the vid and listen instead of typing out this gotcha.)

[@traywor1615]

So: 999 +001 ___ 000 -> throw new OverflowException();

[@brandon406100]

Is zero to the power of zero equal to one?

[@profdaveb6384]

There's several comments already to the effect that my statement " ... anything to the power zero is one" does *not* apply to the special case of 0^0.. Visit our sister channel, Numberphile, and you'll find that there's a video that covers this topic. But note that 0^0 is a serious (possibly headache-inducing ?! ) mathematical challenge.

[@Lightningblade67]

Wouldn't it be ironic if this video overflows the int64 view counter?

[@Lightningblade67]

zemerick13 Well, why didn't IPv6 then use 64 bit? And I'm just saying that is WOULD be funny. Not that it ever WILL be

[@zemerick]

Lightningblade IPv6 uses 128-bit. There's a few reasons for this: The addresses are assigned in chunks. Not all of them may actually be used, so you don't need to fill out every single address in total, to still have problems in certain spots. Also, they want to really future-proof it this time around. Even if some form of "nano-bots" takes off, we could have a unique IP for each of those bots into the billions per person. ( The actual number depends very heavily on how exactly the addresses are handed out, and how many are available. NTM how many people there might be in the future. ) I know you were just joking around, I just found it a good time to have a little fun with just how big of a number that is. Oh, in case you were curious: The unsigned 128-bit of IPv6 is 340 Undecillion. Yea, I would have to look that up just to find out how many 0s there are ( 36 if I did the math right. )

[@OOZ662]

You just had to make this the day after I upgraded my ancient 32bit machine from 3GB to 4GB of installed RAM (expecting maybe a .5GB increase) only to discover that it refuses to address exactly 1024 new MB, didn't you? Abloobloobloo...

[@Dayanto]

The interesting thing about 32 bit and RAM is that theoretically, you should be able to address a full 4GiB, but in practice you can't, because the OS uses the same range of numbers to access the RAM as a bunch of other stuff such as your graphics memory, making the actual limit much smaller.

[@OOZ662]

***** Yep, though even making considerations for other places that ought to be reserving memory space, it shouldn't come near 1GB. It's more likely just my BIOS being dumb.

[@amirhosseingholamshahi4476]

Anthony Hopkins new career!

[@frollard]

Almost too elementary -- but you have to start somewhere so I'm not complaining :)

[@gardinustaung]

To fix a overflow problem just do overflow: hidden;

[@RyanSmith-nf7kk]

That would only cut off digits to the right.. Unless you change the text-align to left.

[@russellchido]

"You want to right out two but you're not allowed TWO." xD

[@inxeoz]

ee haaa haaa eeeya.... 😁

[@pablosaavedra9871]

just 6:15

[@peteranderson037]

Wait, doesn't 1101 = -5?

[@MrYogurtGuy]

If you were to use binary like decimal in mathematics, you'd have to use the standard minus sign for negative numbers. On a computer a 4-bit value of 1101 can either represent 13 or -3. These values are called unsigned and signed respectively (signifying wheter the first bit can indicates a negative value). The first bit doesn't just act like a minus sign though (which is how you got to -5 I assume). It just tells you to start counting from the lowest negative number, which is -8 in case of a 4-bit signed value. So 1111 would be the highest negative value, i.e. -1 (zero is counted as a positive value)

[@peteranderson037]

My dyslexia kicked in. I meant to write 1011, which is -5 in twos complement binary and what he used in the video.

[@Anamnesia]

Binary 101?

[@TheEdenCrazy]

Don't you mean binary 1100101 :)

[@Gooberslot]

Now do hex.

[@Gooberslot]

Validifyed Well, the use of letters as numbers is a bit different. I just thought some people might find a video about hex to be interesting.

[@TheObsidianAsh]

0^0 isn't 1....

[@Echin0idea]

I find thinking partly in binary and partly in decimal to be needlessly confusing (for me at any rate). 1+1+1 is not 3 in binary. 3 doesn't exist in binary - 1 +1 +1 is "11". I suppose it's like learning a language - at first you translate everything in your head, but once you get to a certain point you can just think in the new language. Binary is really simple compared to a language - so it doesn't take too long to be able to think directly in binary.

[@Icy233]

He makes sure his face is in the shot every 10 seconds... That's funny, although not very helpful!

[@anssiaurum264]

"Anything to the 0 is 1" Be careful there. Don't forget about 0^0.

[@irulesoveryou]

+Kåpla Kvëhla 0^0 = 1

[@PointB1ank]

+Kåpla Kvëhla What about -5^0? Equals -1

[@aRobeGamr]

+PointB1ank Only in the sense that your depiction could be interpreted as -(5^0) = -1. However, if you meant (-5)^0, then actually the answer is positive 1. Remember that for a

[@PointB1ank]

+aRobeGamr Very true, my mistake.

[@Reydriel]

0^0 implies division by zero, moreover, 0/0, which ISN'T undefined but "indeterminate". It can equal 1, but you can as easily make a case that it equals pi.