Too bad the young people will never experience the 50s - 90s which is when the real tech revolution occurred. These days people google everything and/or use engines or libraries. They lack the understanding of what and why things happen. Now you know why most applications are slow and bloated garbage.
7:09 Love how the professor just subconciously did a closing bracket and even the semicolon hand writing gesture after saying the statement "if (i == 0);".
if (i == 0); is valid grammar my dudes. It's unusual, and it's probably not what Professor Brailsford wrote with his fingers, but it compiles fine in C, C++ and JavaScript.
I received my CS degree way back in the Dark Ages... 1980. 👴🏼 I’ve been in the software field ever since, and I find Professor Brailsford’s videos fascinating, enlightening, and just plain enjoyable. I sometimes wish I were a young undergrad again, so I could study under him. I learned about ones and twos complement early on, of course... but I don’t remember any prof ever talking about WHY we use them in terms of the need to build the hardware most simply. KEEP IT UP, PROF! 👍🏼👍🏼
Watching these videos makes me absurdly giddy. I love learning (and re-learning, in case I've forgotten since college) how this stuff all works at the lowest levels. I wish I had more time to watch them throughout the day, but compiling breaks don't take as long as they used to. :D
This is beyond brilliant. Makes it so much easier when designing little ripple adders and such for ALUs! I especially appreciated the discussion of the rule for overflow. That would have taken me a while to work out. Wonderfully explained. Thank you!
Yeah, this is why I subscribed. Watching this video for the second time and doing the "math" along with professor Brailsford, I feel like I have a greater inherent understanding of how binary numbers are treated in the machines I work with daily. Thank you!
This is a safe place to accept we all fell in love with this guy('s teaching). I think out of the countless tutorials I've watched to actually "get the feel of this topic", this has hit the bestttttt!
Really cool explanation. Even after learning this in school I learned something by watching this, which was how hardware can do overflow detection using 2s complement.
I learned most CS from my grandfather who was an early pioneer in data processing for State Farm and worked there many years. He was around from the days of the IBM 029 system all the way to clusters of PC clone terminals connected to modern mainframes and the internet (still with the choice of either dedicated ISDN, T1/T3, or 56 kilobaud around when he retired in the mid-late 90s). Every time I hear professor Brailsford start talking through a concept like binary addition over pen and paper i'm instantly transported to being shown the same concepts by my grandpa. Such an amazing teacher, and always bringing the context of the invention itself into the explanation of the solution which helps you remember forever.
I have been doing ones complement and two's complement from past two years in my university and no one ever told me how beautiful it was until UA-cam recommended me this after 5 years
Wonderful video! I always enjoy listening to Professor Brailsford, he has a way of telling and introducing the subject matter which is absolutely brilliant.
The ending was a bit confusing but what happens is that you have two bits somewhere in a register that signifies flags. Sign for positive or negative and overflow for out-of-range. These flags are set in hardware automagically whenever the count moves over a specific number in one way or the other. In Arm the place it happens is xPSR - program status register.
Days of struggling with this and finally I stumble upon the perfect video, the one video to clear them all doubts , one video to find all the the right questions, one video to bind all concepts together and at the last the answers to them(doubts :p).
I thought I was an "expert" on this kind of stuff, until I learned about the overflow rule at the end. This kinda gets me excited again about circuitry; very well explained :D
When I professionally coded 8bit assembler applications many years ago I standardised on using his "bad" example of using the leftmost bit as a sign indicator and the rightmost 7 bits as the number. This had big benefits in display and hardware ADC coding, and although you might think it is worse for number adding than twos complement it worked well enough, you just check the sign bit then choose to either add or subtract the number from the total. So there are definitely commercial products out there using this "bad" system.
*A signed bit system is is bad because it's extremely limited in size *1's complement is better, but still bad because there is a positive and negative representation of zero *2's complement gets rid of both issues by just adding 1 to 1's compliment Great video!
Did this back in the day on my "O" level computer studies course - but what they didn't tell us was why 2's complement was so important i.e. hardware optimisation :-)
Aww, he didn't explain 2's complement the easy(ish) way. It's easiest to think of the sign bit as a negative version of whatever that bit would be if there were no negatives. So if you have this: 1000 Then the 1 bit represents -8. If you have this: 1000 0000 Then the 1 bit represents -128. Then it becomes really easy to figure out what the number is, assuming you know what the remaining bits mean on their own. For example, if you have 101, which is 5 in binary, slapping a 1-bit on the front of it would be 5-8 = -3. If you have 010, which is 2, slapping that 1-bit on would be 2-8 = -6. Essentially, just think of the negative bit as a really big negative number, with the rest of the digits being normal. If that bit is turned on, then everything positive you add to the number will make the value get closer and closer to 0 naturally, because it's cancelling out more and more of the big negative value that the sign bit represents.
+LunaticMS This also explains to programmers why signed numbers hold a smaller range of numbers than unsigned numbers. Signed byte = -128 to 127, unsigned byte (or char in C) is 0 to 255.
It's not a smaller range though it's just shifted. A byte can represent 256 numbers: -128 to 127 is 256 numbers, 0 to 255 is also 256 numbers. Making it unsigned just signals the compiler not to treat it as 2's compliment so 1000 0000 would be 128 not -128
My own preference is to see it in terms of wrap-around (think odometers). With 4 bits, the numbers 0 and 16 are equivalent (0000 vs 1,0000). -1 is the number before 0, which is equivalent to 16-1 = 15, which is 1111 in binary. -2 ~ 16-2 = 14, etc.
6 років тому+1
I liked to think as getting a negative number is substracting the number from 10000 (as many 0s as we use)
I love watching this guy's vids, he really knows his stuff. Edit: BTW, this guy has taught me so much, I always end up trawling through maths articles afterwards.
Very instructive. I learned assembler-programming on a UNIVAC-1100 and machine code programming on a Z80 (I could not quite afford an assembler at first) so I did learn 1's complement and 2's complement. And I can still drive the younger programmers mad by this. Not that I have any use of 1's complement today.
Very interesting to see the "history" behind $FF meaning -1 and $01 +1. I first found out about this representation when I was trying to understand how different digital sound formats work (PCM signed and unsigned, ADPCM, PWM)
I just remembered another nice thing about two's complement: It makes it easy to convert low-precision to high-precision. If you want to convert signed 8-bit to signed 16-bit, all you have to do is fill the top byte with copies of the top bit of the 8-bit value. Just test for whether the top bit is set, then either OR with 0xff00 or use as-is. You can do it on a single line of C like this: sixteen_bit_val = (eight_bit_val & 0x80) ? 0xff00 | eight_bit_val : eight_bit_val;
An overflow is what happened to the first Ariane V rocket. It was driven by the same code as Ariane IV, but its acceleration was so great it overflowed, leading to the most sharp turn ever tried by a rocket.
The famous 6502 doesn't do anything except addition. If you SBC (subtract with carry), you must Set the Carry before the action. The chip (evidently) does a EOR 255 on the subtrahend. You set the Carry, which is the +1 of 2's Compliment. Brilliant!
Wow... doing computer for almost 40 Years, and also did some assembly in my younger times... but never realized before for having two zeros for binary signed numbers...
I wrote a bitwise multiplier one time. It unexpectedly worked for negative numbers somehow. At that point, I decided to stop worrying and love the 2's Complement.
In the pre-360 world, the IBM 700/7000 series used sign and magnitude for their 36-bit binary integer arithmetic, adding the extra hardware to account for signs and overflows properly. Some programming languages, such as FORTRAN, used -0 to represent a word to which no value has yet been assigned; their compiled instructions tested for -0 before performing an operation, and knew that a programming error had occurred (using an uninitialized variable) if -0 was found. No arithmetic operation would ever GENERATE a -0 result; it could only appear as a result of copying a constant into it, or compiling an object program with that value (octal 400000000000, or in the hex notation devised later for the 360 series, 800000000) loaded into all variables with no initial value specified by the programmer. Strangely, although integer math in the later 360 (introduced in 1965) used twos complement notation, FLOATING point math used sign-plus-true magnitude for the mantissa (significant digits) and an excess-64 notation of powers of 16 for the exponent (order of magnitude): in a 32-big (single precision) floating point number, the first bit was the sign (1 for negative) of the entire number, the next 7 bits represented the power of 16 plus 64 (0000000 meant 16^(-64), 1000000 meant 16^0, and 1111111 meant 16^63), and the remaining 24 bits represented a binary fraction. Double precision (64 bits) and extended precision (128 bits) kept the sign and magnitude the same and added the extra 32 (thus a total of 56) or 96 (for a total of 120) bits to the mantissa. I suspect the reasons were that (a) floating point required more complex logic anyway, so temporarily generating twos complement for addition and subtraction were not much extra effort, (b) adding precision only required appending zero bits to the right, not the current value of the sign bit, and (c) more multiplying and dividing than adding and subtracting are done in the areas where floating point is commonly used, and those operations ignore the signs until the end, then determine the sign of the result from the signs of the operands.
A nice property of 2s Complement is that ctz(n) = binaryTrialDiv(n) regardless of the sign of n. What this means is that the number of bitwise trailing zeros always corresponds to the number of times the number can be divided by 2, this accelerates the computation of CTZ by removing a conditional branch. But the real question is, why not use Binary Offsef? It's the same as 2s Complement but with a flipped sign bit, it has the property that all numbers are sorted mathematically, negatives are lower and positives are higher. It also has the nice feature that you only need 1 addition by an offset proportional to the word size of the register, which removes the need for a bitwise-not operation. The only downside I see is that the Offset is only constant if you use the same word-size, since every word of different length requires a different offset
A simpler way of looking at two's complement is considering it arithmetic modulo 2^32. That way there is no difference in operations (except overflow) for signed or unsigned integers. The interpretation of the range from 2^31 to 2^32-1 is just shifted down by 2^32, so it matches -2^31 to -1.
It's funny if you use abs() function for example in C the absolute value of your lowest negative number will be... suprise: the negative number itself (despite manual page saying answer of abs() is always positive number :P). Thanks to having one negative number more than positive, be carefull with abs() - better to write your own and better to remember that. In fe 16b: -32768 exists, 32768 doesn't.
// True, errno isn't even set either. Scary! # include # include # include using namespace std; int main(){ signed short a = 0x7FFF; int erra = errno; signed short b = a+1; int errb = errno; signed short c = abs(b); int errc = errno; cout
One solution to this problem is to avoid abs() and instead use nabs(). If you don't have nabs() create that utility function on your own [nabs(in) { return (in < 0) ? in : -in; }]. It is supposed to return the negative of the absolute value of the input, which always works. Also, check out the book "Hacker's Delight".
***** "nabs" is the opposite of "abs" in that it returns the "negative absolute value" of a number, which can always be expressed in 2's complement. The negative absolute value of a negative number is the number itself. The negative absolute value of a positive number, is the negative of it.
Kai Kunstmann I have been thinking about abs before this and how to get the functionality of abs without the problems with the minimum value. Never thought about using the negative absolute value... Thanks for the info! It might prove useful one day.
There was an overflow bug in Micropose's Railroad Tycoon - if you bought more than 50% of the shares in your company (so you couldn't be thrown out) and then ran the railway in the most inefficient, loss making way possible, your cash would decrease through the negatives (overdrawn balance) until it overflowed and you ended up with the largest amount of positive cash; IIRC making money at this stage did not overflow back negative
I want my alarm clock to wake me up by the sound of 9:08 BTW for some reason I felt a big relief after he explained how to get rid of that negative zero.
About a third of my computer career was spent working with one’s complement machines. They worked well. The extra zero was not a big deal. The hardware took care of it.
Good lesson on binary flaw thanks how about address mode is there any issue and I notice there are problem in Unicode as well if you could have a lesson on those and is there any history on it. Happy to know thankyou very much.
Huh, yeah, there are 15 integers to count, even though it's a "distance" of 14. Maybe he didn't count 0 as an integer because of the whole +/- 0 thing (zero is "two integers"-or more correctly, has two representations-in 1's complement).
The explanation I found easiest to understand is that of the "additive inverse" or the number you add to something to make it "go away" or rather, to make all but the highest digit zero. This is effectively the negative of the number if you drop the top digit. So, the inverse of 25 is75, because 25+75=100 and you drop the 1. So to subtract 25 from, say, 50, you add 75 instead and get 125, drop the 1, 25 is 50-25. Another example: The inverse of 2 is 8 because 2 and 8 are 10 (drop the 1). So to subtract 2 from 7 for example, just add 7 and 8 which is 15, drop the 1, answer is 5. We we work with a fixed number of digits, dropping the 1, the overflow, is easy... and only requires a small adjustment to the way we find the inverse. Let's say we will stick to 4 digits always. That makes the inverse of 25 (actually 0025) become 9975. And the inverse of 0002 is 9998. Everything still works, 0050+9975=(1)0025, and 0007+9998=(1)0005. We just have to remember that the convention of not writing leading zeros and always expanding to the left as far as we need, isn't use.
James Newton Here's the problem: Flipping the sign = doing the inverse and adding 1. The number 50 represents -50; it does not have a positive equivalent in 2's complement. So you do inv(50) = 100-50 = 50. This is saying that 50 = -50.....
Cooper Gates Yes. When working with a fixed number of digits, as we always are in a computer, it doesn't really matter for most basic computations. If you only have 2 digits, it's a more obvious issue, but with 32 bits, or 64, or... it because less of one. And the math package limits or constrains the range of data so that a positive number can not be larger than this halfway point. E.g. in a 2 digit system, the valid range is 49 to -50. If you exceed that range, you get an out of range error. For complex math, you want to transition to floating point or some other system that is more mathematically accurate, but even there we impose limits and can use tricks like this to simplify the computations.
Cooper Gates Yes. -50 * -1 would be an overflow. "because 50 doesn't exist in the system". It's a range error. Still perfectly valid... Is there a system you like better?
James Newton I think it would overflow because the computation would yield -50 again and it would decide that negative * negative should give a positive but it did not so it errors. I've been thinking more about 1's complement and 00 = 99, this is harder in decimal because you have to check for both of those. In binary, you just run an XOR on all the bits and if any two are different you get a 1 out and the number isn't zero. 0000 and 1111 will return 0 for XOR operations of any two of their bits. Then, if you check the sign bit and you have a 1, you use the result from the zero check to see if it's a 0 or an actual negative number.
The point of binary is that computer circuits can detect a charge being either on or off, and charges line up together as bits create a number. You can also make math functions and logical functions. If, then, not, etc. From this you build up entire computing systems, including all the games we play with their fancy graphics. But what if there was a way to store more than the two dimensions of on/off? What if instead of a light switch, on/off, yes/no, you had a dimmer switch that measured the amount of voltage in a circuit? Those 64 bits would be a lot more useful if they could each store ranges of numbers instead of just on or off.
zig-zag, offset (bias), bit signed an base -2 are out there. Does IEEE float use signed magnitude for mantissa and bias for exponent? Google uses zig-zag perchance?
I'd have liked to see a clearer version of that chart in the textbook and an animation of how you shift each system around to get from one to the other. There's such a chart on Wikipedia but I think an animation would make it really clear.
Learning about how computers store numbers is very good :) Just wanted to say it was a bit misleading to bring up undetectable "Not a Number" cases and then describe what is really the carry bit present in all CPUs since the 1970s. I.e. detectable and used a lot in all kinds of software :) I think one important notion is to not get too used to 0 being positive just because it's stored as such in a computer. Oh, you can use it that way eminently in computers and it will turn out right. It's just that it could make you blush for math work. 0 is signless and has no unit. Moving on... have fun coding :)
Challenge: design a hardware circuit to do addition to add two Base -2 numbers. Compare that to the (half/full)-adder-all-the-way-up for 2's complement calculation (which is already worked very well in unsigned calculation as the video says) and you will see why we use 2's complement for negative numbers.
PiHung Liu I didn't say the system was smart, just that it got around using the bits in reverse order as negatives, because negative numbers are naturally represented. The addition rules would likely be even weirder than the order of the numbers themselves
Nikolaj Lepka Hey man, im really confused. I think it is because of the fact I never even thought about something different than a decimal system. I understand it, but could you explain (just like you did for negadecimal 18195 to 2015) example why in a negadecimal system.. 10 (in our decimal system) = 190 in negadecimal. Why is this? I can't get this
michaelyouth because ever other numeric place from the right is negative. In a normal base 10 system you have 1000's 100's 10's 1's so 1000 + 200 + 30 + 4 = 1234 (in base +10) but in a negative one you have -1000's 100's -10's 1's so -1000 + 200 -30 + 4 = -826 (in base +10) so, the negadecimal number 190 = 100 - 90 + 0 = 10 (in +10) also in decimal: 1 = 1 * 10^0 2 = 2 * 10^0 10 = 1 * 10^1 20 = 2 * 10^1 100 = 1 * 10^2 etc whereas negadecimal behaves like this 1 = 1 * (-10)^0 2 = 2 * (-10)^0 -10 = 1 * (-10)^1 100 = 1* (-10)^2
Nikolaj Lepka Thank you, its gotten a bit more clear, but if you were to prove that 10 = 190. So if the question would be: what is 10 in our +10 numeral system, converted to negadecimal. Negadecimal to decimal would be like you said: 190 in negadecimal is 100-90+0 = 10 ( in 10+) but now the other way around: 10 to negadecimal, (would be 190), how do you write that down
I like how he gives the context of the era along with the story… because he was there, he lived it! What a great teacher!
Too bad the young people will never experience the 50s - 90s which is when the real tech revolution occurred. These days people google everything and/or use engines or libraries. They lack the understanding of what and why things happen. Now you know why most applications are slow and bloated garbage.
7:09 Love how the professor just subconciously did a closing bracket and even the semicolon hand writing gesture after saying the statement "if (i == 0);".
haha I didnt see that! Thanks for pointing that out!
@TheSpecialistGamerX2 He clearly says "in your Java program"
It’s an opening curly bracket, “if (i == 0) {”
no he was doing a curly bracket, if you put a semi colon there your compiler calls you a fookin donkey
if (i == 0); is valid grammar my dudes. It's unusual, and it's probably not what Professor Brailsford wrote with his fingers, but it compiles fine in C, C++ and JavaScript.
None of my professor is as energetic and enthusiastic while teaching like him. Hats off professor 🤩🤩
he isnt wearing hats
I received my CS degree way back in the Dark Ages... 1980. 👴🏼
I’ve been in the software field ever since, and I find Professor Brailsford’s videos fascinating, enlightening, and just plain enjoyable. I sometimes wish I were a young undergrad again, so I could study under him.
I learned about ones and twos complement early on, of course... but I don’t remember any prof ever talking about WHY we use them in terms of the need to build the hardware most simply.
KEEP IT UP, PROF! 👍🏼👍🏼
ok?
Watching these videos makes me absurdly giddy. I love learning (and re-learning, in case I've forgotten since college) how this stuff all works at the lowest levels. I wish I had more time to watch them throughout the day, but compiling breaks don't take as long as they used to. :D
This is beyond brilliant. Makes it so much easier when designing little ripple adders and such for ALUs! I especially appreciated the discussion of the rule for overflow. That would have taken me a while to work out. Wonderfully explained. Thank you!
false.
Yeah, this is why I subscribed. Watching this video for the second time and doing the "math" along with professor Brailsford, I feel like I have a greater inherent understanding of how binary numbers are treated in the machines I work with daily. Thank you!
This is a safe place to accept we all fell in love with this guy('s teaching). I think out of the countless tutorials I've watched to actually "get the feel of this topic", this has hit the bestttttt!
Nice camera/focus work on the close-ups on the paper. That was seamless and some high-end professional work.
Really cool explanation. Even after learning this in school I learned something by watching this, which was how hardware can do overflow detection using 2s complement.
4 years of undergrad and just now I really understand 1s n 2s complement, thank you Computerphile
ok?
Clear explanation, Finally I am clear about 2's complement. Thank you sir. I wish I have a teacher like you.
I learned most CS from my grandfather who was an early pioneer in data processing for State Farm and worked there many years. He was around from the days of the IBM 029 system all the way to clusters of PC clone terminals connected to modern mainframes and the internet (still with the choice of either dedicated ISDN, T1/T3, or 56 kilobaud around when he retired in the mid-late 90s).
Every time I hear professor Brailsford start talking through a concept like binary addition over pen and paper i'm instantly transported to being shown the same concepts by my grandpa. Such an amazing teacher, and always bringing the context of the invention itself into the explanation of the solution which helps you remember forever.
I have been doing ones complement and two's complement from past two years in my university and no one ever told me how beautiful it was until UA-cam recommended me this after 5 years
By far the best explanation of two's complement I've found. Thanks!
Wonderful video! I always enjoy listening to Professor Brailsford, he has a way of telling and introducing the subject matter which is absolutely brilliant.
The ending was a bit confusing but what happens is that you have two bits somewhere in a register that signifies flags. Sign for positive or negative and overflow for out-of-range. These flags are set in hardware automagically whenever the count moves over a specific number in one way or the other.
In Arm the place it happens is xPSR - program status register.
The twos complement math works logically even if there are no flags. What you are pointing out is an extra function.
I wish these videos were around back in the days when I was at college....
There just weren't enough bits back then.
Yeah really glad to be an adult student when things have changed.
I hear you and I’m incredibly fortunate to be that college kid :))
This was taught better in my college 20 years ago
Better late then never
This is so much clearer than what my professor told me! Thank you.
Days of struggling with this and finally I stumble upon the perfect video, the one video to clear them all doubts , one video to find all the the right questions, one video to bind all concepts together and at the last the answers to them(doubts :p).
I thought I was an "expert" on this kind of stuff, until I learned about the overflow rule at the end. This kinda gets me excited again about circuitry; very well explained :D
I had computer architecture last year and these videos are still interesting
same. :)
ok?
This man is an absolute legend in the world of mathematics and computer science
Prof. Brailsford is amazing, thanks for the video!
I really like Prof Brailsford.
Incredible video. Really solidified 2’s and 1’s compliment in my head after being confused in class. Thanks for this video!!
When I professionally coded 8bit assembler applications many years ago I standardised on using his "bad" example of using the leftmost bit as a sign indicator and the rightmost 7 bits as the number.
This had big benefits in display and hardware ADC coding, and although you might think it is worse for number adding than twos complement it worked well enough, you just check the sign bit then choose to either add or subtract the number from the total.
So there are definitely commercial products out there using this "bad" system.
*A signed bit system is is bad because it's extremely limited in size
*1's complement is better, but still bad because there is a positive and negative representation of zero
*2's complement gets rid of both issues by just adding 1 to 1's compliment
Great video!
Professor Brailsford is as illuminating as always.
This man is fascinating. So knowledgeable and he was there as this stuff was being developed. Great storyteller and teacher... thanks
thank you so much, i came into this not understanding two's complement at all, and now i feel like i really get it!
Long overdue videp lecture. Thanks to Sean and Professor Brailsford for making this :)
I love this video! the professor's explanation skills are extraordinary!
Did this back in the day on my "O" level computer studies course - but what they didn't tell us was why 2's complement was so important i.e. hardware optimisation :-)
I love this guy... I could watch his videos all day long.
Aww, he didn't explain 2's complement the easy(ish) way. It's easiest to think of the sign bit as a negative version of whatever that bit would be if there were no negatives. So if you have this:
1000
Then the 1 bit represents -8. If you have this:
1000 0000
Then the 1 bit represents -128. Then it becomes really easy to figure out what the number is, assuming you know what the remaining bits mean on their own. For example, if you have 101, which is 5 in binary, slapping a 1-bit on the front of it would be 5-8 = -3. If you have 010, which is 2, slapping that 1-bit on would be 2-8 = -6.
Essentially, just think of the negative bit as a really big negative number, with the rest of the digits being normal. If that bit is turned on, then everything positive you add to the number will make the value get closer and closer to 0 naturally, because it's cancelling out more and more of the big negative value that the sign bit represents.
+LunaticMS This also explains to programmers why signed numbers hold a smaller range of numbers than unsigned numbers. Signed byte = -128 to 127, unsigned byte (or char in C) is 0 to 255.
It's not a smaller range though it's just shifted. A byte can represent 256 numbers: -128 to 127 is 256 numbers, 0 to 255 is also 256 numbers. Making it unsigned just signals the compiler not to treat it as 2's compliment so 1000 0000 would be 128 not -128
I found "2's complement = 1's complement + 1" easier to understand. To undo the operation just minus 1 and take the 1's complement again.
My own preference is to see it in terms of wrap-around (think odometers). With 4 bits, the numbers 0 and 16 are equivalent (0000 vs 1,0000). -1 is the number before 0, which is equivalent to 16-1 = 15, which is 1111 in binary. -2 ~ 16-2 = 14, etc.
I liked to think as getting a negative number is substracting the number from 10000 (as many 0s as we use)
I'm glad someone solved this before I came around. Thank you mysterious person!
I love watching this guy's vids, he really knows his stuff. Edit: BTW, this guy has taught me so much, I always end up trawling through maths articles afterwards.
Very instructive. I learned assembler-programming on a UNIVAC-1100 and machine code programming on a Z80 (I could not quite afford an assembler at first) so I did learn 1's complement and 2's complement. And I can still drive the younger programmers mad by this. Not that I have any use of 1's complement today.
Very interesting to see the "history" behind $FF meaning -1 and $01 +1.
I first found out about this representation when I was trying to understand how different digital sound formats work (PCM signed and unsigned, ADPCM, PWM)
this was a 'bit' confusing. i'll re-watch it, that should help.
Maybe try flipping your monitor upside down.
@@AkshayAradhya you mean GOTO display settings and invert the colors?
Just don’t byte off more than you can chew!
I am pretty sure you waited your entire life to make this joke
Me and the boys designing micro processors
Thanks for this. I had a vague understanding of this, but I was never quite clear on it. This really cleared this up for me.
I just remembered another nice thing about two's complement: It makes it easy to convert low-precision to high-precision.
If you want to convert signed 8-bit to signed 16-bit, all you have to do is fill the top byte with copies of the top bit of the 8-bit value. Just test for whether the top bit is set, then either OR with 0xff00 or use as-is.
You can do it on a single line of C like this:
sixteen_bit_val = (eight_bit_val & 0x80) ? 0xff00 | eight_bit_val : eight_bit_val;
Great explanation, now I got to understand how hardware overflow is detected.
A perfect explanation of negative binary arithmetic.
5 years and only 6K likes, oh UA-cam, you should recommend videos from this channel to every individual engineer.
Professor Brailsford, you splendid man! Thank you thank you thank you. Now I wish he explained how these get turned into hardware.
Other than Tom Scott, Professor Brailsford is my favorite presenter on this channel!
Nice explanantion.. Cleared the concept pretty easily....
@9:10 Yipee. That was the best explanation to one's and two's ever
The best speaker in all videos. Love him!
An overflow is what happened to the first Ariane V rocket. It was driven by the same code as Ariane IV, but its acceleration was so great it overflowed, leading to the most sharp turn ever tried by a rocket.
I have been doing java since start of 2015 and this is relevant!
4:46 Such an UK reaction :d Prof Brailsford is amazing.
The hardware overflow indication was brilliant.
The famous 6502 doesn't do anything except addition. If you SBC (subtract with carry), you must Set the Carry before the action. The chip (evidently) does a EOR 255 on the subtrahend. You set the Carry, which is the +1 of 2's Compliment. Brilliant!
Wow... doing computer for almost 40 Years, and also did some assembly in my younger times... but never realized before for having two zeros for binary signed numbers...
I wrote a bitwise multiplier one time. It unexpectedly worked for negative numbers somehow. At that point, I decided to stop worrying and love the 2's Complement.
The video is a pure treasure
Worthy of note, most of Seymour's CDC systems (6000, 7000, Cyber 70 & 170) used 1's comp.
In the pre-360 world, the IBM 700/7000 series used sign and magnitude for their 36-bit binary integer arithmetic, adding the extra hardware to account for signs and overflows properly. Some programming languages, such as FORTRAN, used -0 to represent a word to which no value has yet been assigned; their compiled instructions tested for -0 before performing an operation, and knew that a programming error had occurred (using an uninitialized variable) if -0 was found. No arithmetic operation would ever GENERATE a -0 result; it could only appear as a result of copying a constant into it, or compiling an object program with that value (octal 400000000000, or in the hex notation devised later for the 360 series, 800000000) loaded into all variables with no initial value specified by the programmer.
Strangely, although integer math in the later 360 (introduced in 1965) used twos complement notation, FLOATING point math used sign-plus-true magnitude for the mantissa (significant digits) and an excess-64 notation of powers of 16 for the exponent (order of magnitude): in a 32-big (single precision) floating point number, the first bit was the sign (1 for negative) of the entire number, the next 7 bits represented the power of 16 plus 64 (0000000 meant 16^(-64), 1000000 meant 16^0, and 1111111 meant 16^63), and the remaining 24 bits represented a binary fraction. Double precision (64 bits) and extended precision (128 bits) kept the sign and magnitude the same and added the extra 32 (thus a total of 56) or 96 (for a total of 120) bits to the mantissa.
I suspect the reasons were that (a) floating point required more complex logic anyway, so temporarily generating twos complement for addition and subtraction were not much extra effort, (b) adding precision only required appending zero bits to the right, not the current value of the sign bit, and (c) more multiplying and dividing than adding and subtracting are done in the areas where floating point is commonly used, and those operations ignore the signs until the end, then determine the sign of the result from the signs of the operands.
Fgxd
Ghhh
I like how happy he got when +0 and -0 mapped to the same binary representation. It's almost like he won the lottery.
A nice property of 2s Complement is that ctz(n) = binaryTrialDiv(n) regardless of the sign of n. What this means is that the number of bitwise trailing zeros always corresponds to the number of times the number can be divided by 2, this accelerates the computation of CTZ by removing a conditional branch.
But the real question is, why not use Binary Offsef? It's the same as 2s Complement but with a flipped sign bit, it has the property that all numbers are sorted mathematically, negatives are lower and positives are higher. It also has the nice feature that you only need 1 addition by an offset proportional to the word size of the register, which removes the need for a bitwise-not operation.
The only downside I see is that the Offset is only constant if you use the same word-size, since every word of different length requires a different offset
A simpler way of looking at two's complement is considering it arithmetic modulo 2^32. That way there is no difference in operations (except overflow) for signed or unsigned integers. The interpretation of the range from 2^31 to 2^32-1 is just shifted down by 2^32, so it matches -2^31 to -1.
FINALLY!!! I now understand what overflow means. Thank you!!!
You Sir are a gentleman and a scholar, great video
It's funny if you use abs() function for example in C the absolute value of your lowest negative number will be... suprise: the negative number itself (despite manual page saying answer of abs() is always positive number :P). Thanks to having one negative number more than positive, be carefull with abs() - better to write your own and better to remember that. In fe 16b: -32768 exists, 32768 doesn't.
// True, errno isn't even set either. Scary!
# include
# include
# include
using namespace std;
int main(){
signed short a = 0x7FFF; int erra = errno;
signed short b = a+1; int errb = errno;
signed short c = abs(b); int errc = errno;
cout
Beesman The standard clearly states that in case of abs() "if the result cannot be represented, the behavior is undefined."
One solution to this problem is to avoid abs() and instead use nabs(). If you don't have nabs() create that utility function on your own [nabs(in) { return (in < 0) ? in : -in; }]. It is supposed to return the negative of the absolute value of the input, which always works. Also, check out the book "Hacker's Delight".
***** "nabs" is the opposite of "abs" in that it returns the "negative absolute value" of a number, which can always be expressed in 2's complement. The negative absolute value of a negative number is the number itself. The negative absolute value of a positive number, is the negative of it.
Kai Kunstmann I have been thinking about abs before this and how to get the functionality of abs without the problems with the minimum value. Never thought about using the negative absolute value... Thanks for the info! It might prove useful one day.
I would like to "compliment" you on an excellent presentation
There was an overflow bug in Micropose's Railroad Tycoon - if you bought more than 50% of the shares in your company (so you couldn't be thrown out) and then ran the railway in the most inefficient, loss making way possible, your cash would decrease through the negatives (overdrawn balance) until it overflowed and you ended up with the largest amount of positive cash; IIRC making money at this stage did not overflow back negative
Final solution seems to creation justification for XORs! Nice.
Simply impressive explanation
very good video. the small printout is rather out of focus most of the time though, while the handwritten is much clearer.
you are very smart mister.
you made it look so easy.
Wow fantastic explanation! Thank you so much!
The last bit... that last example... I never understood binary addition... or numbers, until now! :D
Love this guy, so calming.
I want my alarm clock to wake me up by the sound of 9:08
BTW for some reason I felt a big relief after he explained how to get rid of that negative zero.
About a third of my computer career was spent working with one’s complement machines. They worked well. The extra zero was not a big deal. The hardware took care of it.
great review of the topic
Genius! Right now I am so curious how did they invented this system
Good lesson on binary flaw thanks how about address mode is there any issue and I notice there are problem in Unicode as well if you could have a lesson on those and is there any history on it. Happy to know thankyou very much.
02:00 From -7 to +7, there's 15, not 14, because you have to count 0 too.
Huh, yeah, there are 15 integers to count, even though it's a "distance" of 14. Maybe he didn't count 0 as an integer because of the whole +/- 0 thing (zero is "two integers"-or more correctly, has two representations-in 1's complement).
need more likes to bump this comment up
I'm pretty sure he said that because he wanted to talk about +0 and -0 separately
Thanks for the complete explanation.
2:12 it is 15 different numbers i.e. -7 to 0 and 0 to +7
love camera work, live action.
The explanation I found easiest to understand is that of the "additive inverse" or the number you add to something to make it "go away" or rather, to make all but the highest digit zero. This is effectively the negative of the number if you drop the top digit.
So, the inverse of 25 is75, because 25+75=100 and you drop the 1. So to subtract 25 from, say, 50, you add 75 instead and get 125, drop the 1, 25 is 50-25.
Another example: The inverse of 2 is 8 because 2 and 8 are 10 (drop the 1). So to subtract 2 from 7 for example, just add 7 and 8 which is 15, drop the 1, answer is 5.
We we work with a fixed number of digits, dropping the 1, the overflow, is easy... and only requires a small adjustment to the way we find the inverse. Let's say we will stick to 4 digits always. That makes the inverse of 25 (actually 0025) become 9975. And the inverse of 0002 is 9998. Everything still works, 0050+9975=(1)0025, and 0007+9998=(1)0005. We just have to remember that the convention of not writing leading zeros and always expanding to the left as far as we need, isn't use.
James Newton Here's the problem: Flipping the sign = doing the inverse and adding 1. The number 50 represents -50; it does not have a positive equivalent in 2's complement. So you do inv(50) = 100-50 = 50. This is saying that 50 = -50.....
Cooper Gates Yes. When working with a fixed number of digits, as we always are in a computer, it doesn't really matter for most basic computations. If you only have 2 digits, it's a more obvious issue, but with 32 bits, or 64, or... it because less of one. And the math package limits or constrains the range of data so that a positive number can not be larger than this halfway point. E.g. in a 2 digit system, the valid range is 49 to -50. If you exceed that range, you get an out of range error. For complex math, you want to transition to floating point or some other system that is more mathematically accurate, but even there we impose limits and can use tricks like this to simplify the computations.
James Newton You still can't multiply -50 by -1 because 50 doesn't exist in the system. If you negate -50 you get the same representation.
Cooper Gates Yes. -50 * -1 would be an overflow. "because 50 doesn't exist in the system". It's a range error. Still perfectly valid... Is there a system you like better?
James Newton I think it would overflow because the computation would yield -50 again and it would decide that negative * negative should give a positive but it did not so it errors. I've been thinking more about 1's complement and 00 = 99, this is harder in decimal because you have to check for both of those. In binary, you just run an XOR on all the bits and if any two are different you get a 1 out and the number isn't zero. 0000 and 1111 will return 0 for XOR operations of any two of their bits. Then, if you check the sign bit and you have a 1, you use the result from the zero check to see if it's a 0 or an actual negative number.
Set a hardware overflow indicator, like a boss. :D
i am unqualified to watch this video, but thoroughly enjoy pretending that I understand what he's saying. I admire these humans immensely
very useful for knowing when and how NOT to overflow..
Lovely video and great explanation! Thanks a lot!
The point of binary is that computer circuits can detect a charge being either on or off, and charges line up together as bits create a number. You can also make math functions and logical functions. If, then, not, etc. From this you build up entire computing systems, including all the games we play with their fancy graphics.
But what if there was a way to store more than the two dimensions of on/off? What if instead of a light switch, on/off, yes/no, you had a dimmer switch that measured the amount of voltage in a circuit? Those 64 bits would be a lot more useful if they could each store ranges of numbers instead of just on or off.
You just described an analog computer.
zig-zag, offset (bias), bit signed an base -2 are out there. Does IEEE float use signed magnitude for mantissa and bias for exponent? Google uses zig-zag perchance?
Wish I had him as my professor!
I'm studying for the GATE test, and boy does this help with my confusion in the first chapter.
I'd have liked to see a clearer version of that chart in the textbook and an animation of how you shift each system around to get from one to the other. There's such a chart on Wikipedia but I think an animation would make it really clear.
Learning about how computers store numbers is very good :) Just wanted to say it was a bit misleading to bring up undetectable "Not a Number" cases and then describe what is really the carry bit present in all CPUs since the 1970s. I.e. detectable and used a lot in all kinds of software :)
I think one important notion is to not get too used to 0 being positive just because it's stored as such in a computer. Oh, you can use it that way eminently in computers and it will turn out right. It's just that it could make you blush for math work. 0 is signless and has no unit. Moving on... have fun coding :)
Anyone watch this vedio in 2024, like my comment that it reminds me such nice professor. SPecial respect and too much love
Wow! I'm a Senior Software Developer with 5 years of experience, but I still find that video interesting and a bit fascinating. Bravo! :)
We should just use Base -2, thus avoiding the problem completely. It's messy, but it works, as illogical as it looks, it's still possible to make every number using it.
0 0000 = 0
0 0001 = 1 = (-2)^0
0 0010 = -2 = (-2)^1
0 0011 = -1 = ((-2) + 1)
0 0100 = 4 = (-2)^3
0 0101 = 5
0 0110 = 2
0 0111 = 3 = (4 + (-2) + 1)
0 1000 = -8 = (-2)^4
0 1001 = -7
0 1010 = -10
0 1011 = -9
0 1100 = -4
0 1101 = -3 = ((-8) + 4 + 1)
0 1110 = -6
0 1111 = -5 = ((-8) + 4 + (-2) + 1)
1 0000 = 16 = (-2)^4
Base -10 (Negadecimal) works the same way :D
Here's the current year in negadecimal: 18195 = (10000 + (-8000) + 100 + (-90) + 5) = 2015
Challenge: design a hardware circuit to do addition to add two Base -2 numbers. Compare that to the (half/full)-adder-all-the-way-up for 2's complement calculation (which is already worked very well in unsigned calculation as the video says) and you will see why we use 2's complement for negative numbers.
PiHung Liu I didn't say the system was smart, just that it got around using the bits in reverse order as negatives, because negative numbers are naturally represented. The addition rules would likely be even weirder than the order of the numbers themselves
Nikolaj Lepka Hey man, im really confused. I think it is because of the fact I never even thought about something different than a decimal system. I understand it, but could you explain (just like you did for negadecimal 18195 to 2015) example why in a negadecimal system.. 10 (in our decimal system) = 190 in negadecimal. Why is this? I can't get this
michaelyouth because ever other numeric place from the right is negative.
In a normal base 10 system you have
1000's 100's 10's 1's
so 1000 + 200 + 30 + 4 = 1234 (in base +10)
but in a negative one you have
-1000's 100's -10's 1's
so -1000 + 200 -30 + 4 = -826 (in base +10)
so, the negadecimal number 190
= 100 - 90 + 0 = 10 (in +10)
also in decimal:
1 = 1 * 10^0
2 = 2 * 10^0
10 = 1 * 10^1
20 = 2 * 10^1
100 = 1 * 10^2
etc
whereas negadecimal behaves like this
1 = 1 * (-10)^0
2 = 2 * (-10)^0
-10 = 1 * (-10)^1
100 = 1* (-10)^2
Nikolaj Lepka Thank you, its gotten a bit more clear, but if you were to prove that 10 = 190. So if the question would be: what is 10 in our +10 numeral system, converted to negadecimal. Negadecimal to decimal would be like you said: 190 in negadecimal is 100-90+0 = 10 ( in 10+) but now the other way around: 10 to negadecimal, (would be 190), how do you write that down
Love this guy, he's cool and he loves what he does!