Binary: Plusses & Minuses (Why We Use Two's Complement) - Computerphile

going out of bounds if you don't or can't check for it or if your hardware doesn't signal it to you can be really really embarrassing because all sorts of dangerous situations can happen perhaps the most easy one to understand is that yes if you add together two positive numbers that are too big they're going to come out looking like a negative number the the overflow situation will propagate into the sign bit you amp together two things which you've got a zero on the Left saying clearly they're positive when the whole thing overflow is you end up with the answer having a one in the sign bit so it's looking negative if you for example haven't had a digital radio altimeter which was absolutely sure that you were at 30,000 feet and then suddenly found that it to run out of bits and oh dear you've added together the latest increments in height course you've climbed a bit and oh dear you seem to be 60 fathoms deep under the sea things can get very very embarrassing indeed if other hardware that controls your engine or your flaps relies absolutely on this thing being correct I'm going to describe to you in three different ways how you might tackle doing negative numbers whichever notation you use it turns out to be handy to keep the right-hand side of your bit pattern as you look at it the actual magnitude of the number and save the leftmost bit as you're looking at it for denoting the sign and almost universally it will be if that's so called sign bit as it's now called is 0 then it denotes a positive number if it's a one it's going to denote a negative number so roughly speaking if you think about that 0 and 1 signaling the sign that leaves you three bits left for the actual size of the number be it positive or negative well in three bits you can hold anything from zero to seven so roughly what one is saying is that if we have a range of numbers that goes from plus 7 2-7 do you think about it that's 14 do from numbers one to seven positive 1 to 7 negative 14 different numbers but in four bits we can accommodate 16 numbers to the power 4 is 16 naught 2 15 in hand side so where's the other two gone we've allocated for teams to all the other two are real trouble causes because what tends to happen in your naive approach to this which we'll do in a minute is those two missing numbers converge on wanting to be zero so you end up with plus 0 and minus a 0 and that is a pain you start off with zero four zeros here four plus a 0 if you put a one in the sign bit position but leave the others to zero then of course you've got minus zero what could be more nightmarish if you're trying to design a binary adder circuit to say oh we're not just got to check for plus zero we gotta check 4-0 okay and all the rest it just follow exactly like that look 00 01 is +1 so what would minus 1 be same as +1 or not one but put a warm to denote negative at the left hand side and that works all the way in the sign and magnitude notation the example I'm going to take in all three of these notations i'll be covering is just simply this plus 7 and add on minus 3 to it in other words it's seven take away three the answers gots before now where do we get to its sign and magnitude we write down plus seven then we write down 10 11 don't forget this is now the sign bit it's special the note 11 2 and the 1 is 3 but the one in the sign bit position says I'm trying to do 7-3 your hardware man then start saying look I've got to build some binary logic circuitry to do this and what I want is just to do simple binary editions with carys even those a subtraction I don't care you've told me you denoted a negative number I want to do simple binary editions of ones and laws and I want the answer to drop out just magically to plus 4 will it not a chance I'm going to say if you just add them what would happen you get 1 plus 1 is 0 and carry one one and one and one we now know you put down a one and you carry a 1 1 plus 1 is 0 but it carries a bit over into this sign bit column oh what a nightmare what is trying to tell you look is that the answers to it isn't when you come to analyze this carefully it happens largely because the sign bit is not actually part of the number it's an add on extra so this one way I think we can throw right out the window and say it may appeal to you as a human to do it like this but really that is not going to be easy to build hardware around what you want actually in some sense is to map those negative numbers differently in other words you map them top down from the big numbers down to the little ones in terms of what an unsigned the law would be doing the other way around and it all is so much easier what ones complement does is it says form the negative number by taking a positive one and inverting every bit if it's a zero turn it to a one if it's a one turn it to a zero what that does is it turns 0 into being what would have been 15 in unsigned yeah but ah since one on the left is signed and now image is a negative number you still have the two representations of zero problem you've got zero and you've got minus zero however look what happens here you map 0001 you flip all the bits this is a rule to make it negative change 0001 into being 1110 so that is how you do minus one but what does 1110 mean if it were an unsigned number it means a plus 4 plus 2 is 14 so I've mapped minus 1 into being 14 I'm at minus 2 into being 13 this is what i mean by coming downwards okay now if you do that well you're part way on the way to getting a system in which the sign bit behaves almost normally and that's what you want to do let us know let me say yet again this still has the problem of two representations of 0 which hardware and software people would absolutely hate could you imagine in your java program if you wrote if i equals equals 0 behind the scenes a swearing compiler indulges in lots of bad language saying owing to the architecture of this machine now now got to check for plus 0 and minus zero don't want that you want one representation of 0 anyway for the moment this is a step on the way we're getting there this is one's complement and let's do our thing of taking plus seven and adding minus three well since seven is a positive number that is still 0 1 1 1 but we've now got to add in minus 3 well we look up what minus 3 is in one's complement and it is 1100 now what I'm saying is that is a positive representation because it's got not there as plus 7 this is a negative number clearly it is it's got one in the sign bit position let's just add them together one and 0 is 1 1 and 0 is 1 1 and 1 is 0 but carry 11 and 1 is 0 this is in the sign bit position now but we're still treating it now like it's an ordinary binary pair of integers but I've still got 1 plus 1 is 0 and it will generate a caring the rule in one's complement arithmetic says the following treat the sign bit just like a normal binary addition in that position but if you generate a carry out from the sign bit don't throw it away don't ignore it just bring it back on a journey around to the right hand end of the number and add it in so we then have naught naught 1 1 plus 1 1 + 1 is 0 carry 1 1 0 1 is 0 carry 1 1 and 0 is 1 0 and 00 you p that's possible that's the right answer now you might say oh well bringing around that carry bit it's just black magic yeah that would need a more advanced tutorial explaining exactly why but it really does work is simply this it says just treat the sign bit as normal don't get panicked about it if you do generate the carry bit just bring it around to the right hand then and add it back in ok so we're making real progress now we've got something which does give us a right answer but you have to mess about with carry bits a little bit wouldn't it be nice if we could get rid of that effect don't have to worry about any carry bit and also also what we really want to solve is this we dumped 12 zeros ok now there is a big problem here because if you think about it you've got some positive numbers seven negative numbers you've got two left over if you don't have to zeros and you'll know what 10 what's going to happen to that 16th number as we'll find out now in the final phase of this story your leftover number has either got to become an extra positive number or an astronaut Eve number so will now do two's complement two's complement is equivalent to the ones complement with one added to it let's just take a sample middle of the range number plus 3 let's turn it into twos complement and remember what you do to do that is you take the binary representation of three you first of all turn it into one's complement by flipping the bits and then you add one let us take plus 3 this is zero zero one one and we want minus 3 in well first of all we do minus 3 in one's complement easy you just flip the bits you go 1100 and in two's complement what do you do you take the ones complement which you've already got a new add one and you see what happens one plus zero is 10 11 there's your answer so minus 3 in two's complement is represented by 1101 in unsigned terms this has now been represented by 13 1101 whereas in one's complement terms it was 1100 it was represented by 12 so we've shoved at the whole range down by one believe it or not that now magically gets rid of the two zeros problem just by shifting the range and if you like this is the fundamental piece of magic which I think we can do over here just consider 0 0 0 0 plus 0 I'm now going to turn it into minus 0 and with trepidation because it's probably going to be some other completely different bit problem but just look what the rule says it says do the ones complement first of all 11 11 and add one because two's complement is one's coming up this one what happens now 1 1 is 0 carry 1 1 0 1 is 0 carry a 1 1 0 1 is 0 carry 11 and what we're in the side bit position but we don't panic it's just like any other one on one is 0 and we carry one I'm going to do an end-around carry no thing you have to remember in two's complement is that carries at the left-hand end I just thrown away and ignore they do not do an end-around carry why they did in one's complement this magic you just throw the carry bit away and what you're left with no not-not-not look at plus zero has mapped into looking like plus zero when you take it two's complement negative that's exactly what you are after is one representation of zero and only one but you'll now say are now come on you warned us that if you have only 10 and you if you have and one to seven that's seven numbers and minus 1 by seven oh seven times you want 10 that's only 15 slots taken up what's happening to the 16th slot although it's a four bit system it now ranges from 0 to 7 in positive but in negative numbers there's the zero appearing again but right out the bottom one and three zeros what does that one represent that and the answer is minus eight what happens when he goes wrong well it we've discovered of course that in two's complement for bit representation we can go from minus eight up to plus seven you add anything within those ranges as we've been doing like seven plus minus three there's no problem the answer is going to be in range obviously but if you add together shall we say plus 72 plus seven and that's plus 14 and that's too big positive to be held in four bits equally if you had I don't know minus five 2-5 comes to minus 10 and we can go down as far as minus eight but not minus 10 so how does this show up then we clearly going to get overflows well I think the answer is if you look back or think back in the video to what we were doing when we were carefully adding 7 2-3 and staying in range what I didn't point out but should have done at the time is that the carry bit that appeared on the left you remember you carried out of the sign position I said oh it's two's company cuz throw it away yes you can throw it away but what you would find is if it's gone wrong is that there was a carry in to the sign bit before there was a carry out and the rule very simply is this is if they carry in to the sign bit and the carry out to the sign bit are the same sort of thing like you carrying a worn you carry out a one that's fine or you carry in an or you carry out or not that's fine but if they're the opposite way around a naught gets carried into the side bit of one gets carried out or a one gets carried in & anor gets carried out surefire sign of overflow and that is exactly what the hardware engineer wants they don't want to have to start thinking about the magnitude of the numbers they want a simple rule about carry bits which says it overflowed and then you set a hardware overflow indicator just like that this is a problem it hitters and they would have embarrassed us slightly in the Ackermann function video because the those counters we were setting for all the big integers we were overflowing all the time we just weren't checking for it

Channel: Computerphile

Views: 306,252

Rating: 4.971396 out of 5

Keywords: computers, computerphile, Two's Complement, Binary Number, Sign, professor dave brailsford, university of nottingham, signed binary, binary

Id: lKTsv6iVxV4

Length: 16min 15sec (975 seconds)

Published: Wed Jan 28 2015