YT YouTube2Text

YouTube2Text → Transcripts → [CS61C FA20] Lecture 02.4 - Number Representation: Two's Complement, Bias, and Summary

[CS61C FA20] Lecture 02.4 - Number Representation: Two's Complement, Bias, and Summary — Transcript

by CS 61C Departmental · 2,525 words · 411 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00and welcome back now let's see if we can
0:03figure out
0:04what we can do to fix one's compliment
0:07is there anything we can do
0:08and guess what it's called two's
0:10complement we'll also talk about
0:11something called biased encoding
0:14so here's the idea the problem is the
0:16negative numbers overlap with the
0:17positive numbers we saw that we don't
0:19want that
0:19we want to shift the bottom over one so
0:22here's what we do just like before
0:26all the zeros are on the top so like in
0:28the five bits before
0:29all zeros up to zero one one one one
0:32that's all on the top that's zero
0:34through fifteen that's the same so in
0:35terms of the top never really changes
0:36doesn't change actually zero to all ones
0:39doesn't change in
0:40unsigned sine magnitude one's complement
0:43or this two's complement so that's kind
0:44of the top stays the same
0:46it's what happens on the bottom except
0:49all ones we don't want to be zero we
0:51want all ones to be
0:52negative one and in fact i want you to
0:54lock that in all ones is always negative
0:56ones
0:57in this two's complement number okay
1:00it's called two's complement the
1:01hardware is now
1:01really really really easy we went from
1:03being complicated because these two
1:05zeros
1:05to really easy actually um by the way if
1:08you're a c programmer we'll teach you
1:10this next lecture
1:11you're going to see that in c it's
1:12called an int again we don't have how
1:14widened
1:15ins are so we have this thing called int
1:17types we'll tell you into int
1:19i for integer int with a number 8 16 or
1:2264
1:238 16 32 64 etc is a sign integer
1:26and this is two's complement so if you
1:28think of a signed integer
1:30the sign means we're doing this choose
1:32complement signing to be able to handle
1:33negative numbers okay unsigned means
1:35only positive numbers or
1:36only non-negatives zero or positive
1:38numbers
1:40okay here's the formula here's the way
1:42to think of it okay
1:43so for 32 bits the same as before
1:46all the lower bits are the same right
1:49lowest
1:50the lowest um the lowest coefficient
1:53times one the second lowest second
1:55lowest bit
1:56times two the third lowest bit times
1:59four etc
2:00except that you take this big guy
2:04and you say it's multiplied the
2:06coefficient but if the high a bit is
2:08it's that kind of that sign bit really
2:09it's not really a sign because it's not
2:10side magnitude but we think about the
2:12sign bit because
2:12the negative numbers all have a 1 there
2:14so we'll think about the sign bit for
2:16this case even though it's not sine
2:17magnitude
2:18times minus 2 to the 31
2:22minus 2 to the biggest biggest term so
2:24let's do this simple let's go back to a
2:25nibble now not five bits go back to a
2:26nibble four bits
2:28one one oh one well one one on one in
2:31unsigned
2:32well in hex1101 is d memorize that guy
2:35okay
2:36d that was going to be 13. what is it if
2:39we're talking about
2:40choose complement or sign assigned
2:43number two's complement
2:44let's do it again well this is 101 so
2:47this is the
2:48that's two no's one four no two
2:51one one and this is negative eight
2:55so watch this here's your five remember
2:58101 is five
3:00minus eight there's minus three okay
3:04that's one way to think about it minus
3:05three
3:08another way to think about it is flip
3:10the bits and add one
3:12and that's the equivalent number
3:14positively so let's do this
3:16let's flip the bits and add one so
3:19here we go 1 101 flip the bits
3:24001 0. add 1 001
3:28that's the negative of it so if that's a
3:30positive number now it's 3 that means 1
3:31101 must have been negative 3.
3:34let's do that let's reverse it now flip
3:36the bits again
3:381 100 add 1 1 101 and that's negative 3.
3:41so i went from negative 3
3:43to 3 to minus 3. by the way this picture
3:47is an optical illusion some people see a
3:49vas some people see a face
3:51sometimes it flops between a vase and a
3:52face the point of that showing you this
3:54is
3:54i can think of this the way i do it the
3:56way as a pro tip
3:58the way that i think about negative
4:00numbers and how to do them fast
4:01is i actually see when i say okay this
4:04leading one now
4:06i immediately see this and i flip i
4:08treat everyone as a zero into zero one
4:10which means i basically do this in my
4:12head
4:12okay and then i just quickly add one
4:14that s has to be negative three
4:16so i say to myself oh here's this now if
4:19this is the only one
4:20and i add one it's minus three see that
4:23because i
4:24quickly flipped it thinking that's the
4:25only one and if i add one to that
4:27i get all one one and i go back and i
4:29say what's that in decimal
4:30it's three so i'm able to really fast
4:33think about how to do that
4:34fast for yourself so
4:37flip the bits and add one
4:40so here we got a number line this
4:42beautiful number line as i
4:45count around as i'm counting around here
4:48in my binary odometer i've taken my
4:49odometer and kind of made it round
4:51here's the numbers that are being
4:51represented as i do this
4:540 1 2 3 up to 15. this is the same this
4:56is always the same
4:57just like the positive numbers are
4:59always the same 0 through 15. that's
5:01been that way for every
5:02representation we've seen so far all
5:03zeros through zero and all ones
5:05is zero through here in case 15 for five
5:07bits
5:09then it jumps to minus 16.
5:14jumps to minus 16. and you might
5:16remember this last slide watch this
5:18slide here
5:18remember this this is the negative
5:20number
5:22that's this minus 8 that pulls it back
5:24by doing minus 50 minus 16
5:28it took this this representation which
5:31used to be in one's complement minus 15
5:33and then all the ones was here we didn't
5:35want that we wanted to bring it back one
5:37more
5:37so that's why
5:40that term that top level term minus 16
5:43pulls that
5:44down so that this is the minor 16
5:46pulling that value down to minus 16. if
5:47i then stretch
5:4816 more guys or 15 16 more guys there
5:51this will end up at minus one
5:53right minus 16 to minus one is 16 things
5:56so that's why that works that cool
5:58that cool top level term this cool top
6:00level term
6:01it's because you grab that negative guy
6:03that smallest native number and
6:05pulled it over by exactly one and one's
6:07complement minus 15
6:09and now it's minus 16 which is why it
6:11works
6:12so let's look at our odometer now and
6:14let's see if our we have
6:15let's see if i overlap here ready there
6:18we go
6:18there's 0 to 15 and no overlap
6:22and as i said before all ones is
6:25negative one
6:26huh with the thing and then there's all
6:28ones negative one
6:30love it okay two to the n minus one
6:33non-negatives two to the n minus one
6:35negatives
6:36one zero okay how many positives ask
6:39yourself that
6:40and then we'll see this next encoding
6:42which is called
6:44the biased encoding now
6:48one of the things that's interesting is
6:50none of these guys
6:51had negative numbers they could
6:54represent
6:54but also all zeros being the smallest
6:57value
6:58here's here's another here's an analogy
6:59for you i'm recording some electrical
7:02signal okay electrical i'm recording
7:03some electrical signal
7:04and it's wavering from zero volts which
7:06is you know no
7:07no no let's say it's a dc dc voltage to
7:1031 volts okay
7:12and i'm going between that so you know
7:13nothing there and now goes to 31 and
7:15goes down to there
7:16and i want to have 31 different
7:17representations in there well
7:20let's say it's wiggling like this i if
7:22you think about graphing this would be a
7:24graph it's always a positive thing and i
7:25said to myself
7:26wouldn't it be cool to kind of grab this
7:27graph and bring it down so it wiggles
7:29around zero
7:30that's what this does it takes these
7:32values and
7:34pulls them down by some bias that to add
7:37an offset or we call the dc bias it will
7:40if i add negative 15 volts then it now
7:42sudden my signal is wiggling down here
7:44across zero so this bias brings things
7:47down to so it's kind of balanced or
7:48balanced across zero but now you see the
7:50problem is zero is one guy
7:53you're never going to have an equal
7:54number of positives and negatives
7:55because that's a total of
7:57like zero is one thing either you have
7:59two zeros and then an equal number of
8:00positive negatives or
8:01you have one zero which is what we want
8:03and then an unequal number positive
8:04negatives and if you recall
8:06i have one more negative than
8:09positive in a two's complement
8:11representation right i only go to 15
8:13but i go to minus 16 as my biggest
8:15negative okay
8:18in bias we are going to take my numbers
8:21my unsigned numbers 0 through 31
8:24and then add this bias on top of it
8:28pulls it down and what distinguishes it
8:31from that
8:32i could either add minus 16 to it so
8:34they're almost exactly the same as the
8:35two's complement that's not what we do
8:36what we typically do
8:38so by default we're going to have a bias
8:41chosen as minus 2 to the n minus 1 minus
8:441 meaning i got 5 bits here make it 4
8:46bits
8:462 to the 4 is 16 subtract by 1 is 15
8:49minus 15.
8:50that's my bias here okay so if i
8:54grab z all zero here's like here's the
8:56unsigned remember look unsigned pretend
8:58this is unsigned okay unsigned all
8:59zeroes to all one in that order
9:02if i grab it and shift it back by minus
9:0415
9:06what i get is all zeros is now the
9:09smallest negative number
9:11and it just keeps counting up one one
9:13one one one it's actually beautiful this
9:14way
9:15here's my odometer it just does the
9:18right thing
9:19so i start with the smallest negative
9:21number which again is this
9:22this value here and i just keep going up
9:25by one
9:26and nothing strange happens around zero
9:29i just keep incrementing minus one one
9:31nothing strange happens there
9:34unlike before it would snap around it
9:36would wrap and flip no it just continues
9:38to count up
9:39it just just works um you can think
9:42about by the way zero
9:44this is actually the equivalent of the
9:46bias when -15
9:48adds to the unsigned value 15 i get zero
9:51because the number is the unsigned value
9:54plus the bias
9:55okay it'll take some practice but we
9:58really like biased encoding
10:00for some applications and we'll see that
10:01actually later in this course
10:04and in summary we're at the finish line
10:06woo
10:09we represent things in computers as bit
10:12patterns
10:13n bits is two to the n things
10:16we've talked about five integer
10:18encodings each of them have com each of
10:20them have benefits and each of them have
10:22shortcomings one's complement and size
10:25magnitude have the most problems so we
10:26don't use those what we typically use
10:28is the remaining three we use unsigned
10:32choose complement and bias we're going
10:33to see those guys
10:35unsigned comes for free in a programming
10:37language here we go
10:38unsigned numbers are you int in c choose
10:41complement come as ins
10:43or int n underscore t
10:46biased there is no way to do that you
10:48have to almost store the bias together
10:50or remember that and if i'm shipping you
10:52some bits i'll ship you an unsigned
10:54and then i'll encode it for example if
10:56i'm going to store
10:570-31 let's give it a short some numbers
10:59like let's say minus
11:01see oh here we go minus 16 minus
11:0416 minus right here let's go back
11:07my minus 15 to 16. okay i want to store
11:10that number
11:11i'll store this how can i give this to
11:14you
11:14if you and i are agreeing on this
11:16there's no way in the computer do this
11:17but you aren't agreeing on it
11:18what we do is i send your mail saying ps
11:21the bias is going to be -15 and then i
11:23hand you the unsigned value
11:26so i take my number from minus 15 to 16.
11:29okay i add back the bias to find out
11:32what the bit pattern is
11:34okay all right finish it so so now i
11:36have
11:370 to 31. i encode that as a number 031 i
11:41ship it to you
11:42you apply the bias and now it goes back
11:44to the range that i had so i had a
11:45number from -15 to 16
11:46i converted to the unsigned equivalent
11:48of it give it to you
11:50and then you decode that that's the way
11:51you have to do biased
11:53overflow is when it wraps and the bits
11:56aren't enough to store the
11:57the actual number that you want because
11:58numbers are infinite but the the the
12:00numerals and the the space we have is a
12:02finite
12:03value you saw this ain't no free lunch
12:05to get
12:06negative numbers we had to steal
12:08something from the positive space we now
12:10couldn't go to 31 we only go to 15 and
12:12we saw all of them
12:13actually able to go to 15 except for
12:15except for
12:16uh bias which goes to 16.
12:20meta take away from the big big big big
12:22big big picture is we often make
12:25design decisions to make the hardware
12:26simple and one of the reasons we threw
12:28out sine magnitude and one's complement
12:30is that the hardware to build that would
12:31have been really hard but the hardware
12:33to build
12:34unsigned and side magnitude is really
12:36easy and in fact
12:38i give you a secret as we start this is
12:40like i'm foreshadowing probably 10 weeks
12:42ahead
12:42it's the same hardware it's the same
12:45hardware to do mathematics
12:47on unsigned and two's complement
12:51numbers the only thing you have to worry
12:53about is overflow because different
12:54things overflow because they're
12:55different the ranges are different right
12:56the ranges
12:57this is 31 and this is you could you can
12:59do something weird you could overflow
13:00negative there it's a little different
13:01for the overflow calculation but the
13:02rest of it's exactly the same
13:04so it's really cool you can use the same
13:05hardware to add two two's complement
13:07numbers
13:07as you could to add two unsigned numbers
13:10if you don't care about overflow
13:11that's pretty cool that's the end of
13:14this lecture on number representation
13:15folks it was really fun
13:17the next series of the next module will
13:19be a series of lectures
13:20on c programming i'll see you there

About this transcript

This page contains the full transcript of [CS61C FA20] Lecture 02.4 - Number Representation: Two's Complement, Bias, and Summary by CS 61C Departmental, generated from the public captions YouTube serves with the video. The transcript has 2,525 words across 411 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.