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

Full transcript

1. 0:00and welcome back. Now let's see if we
2. 0:03can figure out what we can do to fix
3. 0:06one's complement. Is there anything we
4. 0:08can do? And guess what? It's called
5. 0:10two's compliment. We'll also talk about
6. 0:11something called biased encoding.
7. 0:14So here's the idea. The problem is the
8. 0:16negative numbers overlap with the
9. 0:18positive numbers. We saw that. We don't
10. 0:19want that. We want to shift the bottom
11. 0:21over one. So here's what we do. Just
12. 0:25like before, all the zeros are on the
13. 0:27top. So Z like in the five bits before
14. 0:29all zeros up to 01111 that's all on the
15. 0:33top that's 0 through 15 that's the same.
16. 0:35So it turns out the top never really
17. 0:36changes. Doesn't change actually zero to
18. 0:38all ones doesn't change in unsigned sign
19. 0:41magnitude one's complement or this two's
20. 0:44complement. So that's kind of the top
21. 0:45stays the same. It's what happens on the
22. 0:47bottom
23. 0:49except all ones. We don't want it to be
24. 0:51zero. We want all ones to be negative
25. 0:53one. And in fact I want you to lock that
26. 0:55in. All ones is always negative ones in
27. 0:57this two's complement number. Okay? It's
28. 1:00called two's complement. The hardware is
29. 1:01now really really really easy. We went
30. 1:03from being complicated because there's
31. 1:05two zeros to really easy actually. Um,
32. 1:08by the way, if you're a C programmer,
33. 1:09we'll teach you in this next lecture.
34. 1:11Um, you're going to see that in C it's
35. 1:12called an int. Again, we know how how
36. 1:14wide in ints are. So, we had this thing
37. 1:16called intypes. We'll tell you int i for
38. 1:19integer. Int with a number 8, 16 or 64.
39. 1:238, 16, 32, 64, etc. is a sign integer.
40. 1:26And this is two's complement. So
41. 1:28whenever you think of a signed integer,
42. 1:30the sign means we're doing this choose
43. 1:32complement signing to be able to handle
44. 1:33negative numbers. Okay, unsigned means
45. 1:35only positive numbers or only non-
46. 1:37negatives, zero or positive numbers.
47. 1:40Okay, here's the formula. Here's the way
48. 1:42to think of it. Okay, so for 32 bits,
49. 1:46the same as before. All the lower bits
50. 1:47are the same, right? Lowest the lowest u
51. 1:52the lowest coefficient times one. the
52. 1:55second lowest, second lowest bit times
53. 1:57two, the third lowest bit times four,
54. 1:59etc. Except that you take this big guy
55. 2:04and you say it's multiplied the
56. 2:06coefficient, but of the high a bit is
57. 2:08it's that kind of that sign bit. Really,
58. 2:10it's not really a sign bit because not
59. 2:10sign magnitude, but we think about it as
60. 2:12a sign bit because the negative numbers
61. 2:14all have a one there. So we'll think
62. 2:15about as a sign bit for this case, even
63. 2:16though it's not sign magnitude times
64. 2:19minus 2 31 minus 2 to the biggest
65. 2:23biggest term. So, let's do this simple.
66. 2:24Let's go back to a nibble now. Not five
67. 2:26bits. Go back to a nibble. Four bits.
68. 2:28[snorts] 11 101. Well, 11 101 in
69. 2:31unsigned. Well, in hex 11 is D. Memorize
70. 2:35that guy. Okay, D. That was going to be
71. 2:3713. What is it? If we're talking about
72. 2:41two's complement or sign a signed
73. 2:43number, two's complement. Let's do it
74. 2:45again. Well, this is 101. So, this is
75. 2:48the that's two nos four no two one one.
76. 2:52And this is -8.
77. 2:56So watch this. Here's your five.
78. 2:58Remember 101 is five minus 8. There's
79. 3:02minus3. Okay, that's one way to think
80. 3:04about it. Minus3.
81. 3:09Another way to think about it is flip
82. 3:11the bits and add one. And that's the
83. 3:13equivalent number positively. So let's
84. 3:15do this. Let's flip the bits and add
85. 3:17one.
86. 3:19So here we go. 11 101. Flip the bits.
87. 3:25O10 add one. O11. That's the negative of
88. 3:29it. So if that's a positive number, now
89. 3:30it's three. That means 11 101 must have
90. 3:32been -3. Let's do that. Let's reverse
91. 3:35it. Now flip the bits again.
92. 3:3811 10 add 1 11 101. And that's3. So I
93. 3:42went from -3 to 3 to minus 3. By the
94. 3:45way, this picture is an optical
95. 3:48illusion. Some people see a vase. Some
96. 3:50people see a face. Sometimes it flops
97. 3:51between a vase and a face. The point of
98. 3:53that showing you this is I can think of
99. 3:55this. The way I do it, the way's a pro
100. 3:57tip, the way that I think about negative
101. 4:00numbers and how to do them fast is I
102. 4:02actually see when I say, okay, this
103. 4:04leading one now I immediately see this
104. 4:07and I flip. I treat every one as a zero
105. 4:10and a 0 one, which means I basically do
106. 4:11this in my head. Okay? And then I just
107. 4:14quickly add one. I say it's been
108. 4:15negative three. So I say to myself, oh
109. 4:17here's this. Now if this is the only one
110. 4:20and I add one, it's minus3. See that?
111. 4:23Because I quickly flipped it thinking
112. 4:25that's the only one. And if I add one to
113. 4:27that, I get 011. And then I go back and
114. 4:29I say what's what's that in decimal?
115. 4:30It's three. So I'm able to really fast
116. 4:33think about how to do that fast for
117. 4:34yourself.
118. 4:36So flip the bits and add one.
119. 4:41So here we got a number line. This
120. 4:42beautiful number line. As I count
121. 4:45around, as I'm counting around here in
122. 4:48my binary odometer, I've taken my
123. 4:49odometer and kind of made it round.
124. 4:51Here's the numbers that are being
125. 4:52represented. As I do this, 0 1 2 3 up to
126. 4:5515. This is the same. This is always the
127. 4:57same. Just like the positive numbers are
128. 4:59always the same. 0 through 15. That's
129. 5:01been that way for every representation
130. 5:02we've seen so far. All zeros through
131. 5:04zero and all ones is zero through here
132. 5:06in case 15 for five bits. Then
133. 5:10it jumps to minus 16.
134. 5:14jumps to -6. And you might remember this
135. 5:17last slide. Watch this slide here.
136. 5:19Remember this. This is the negative
137. 5:21number. That's this minus 8 that pulls
138. 5:24it back by doing minus minus 16.
139. 5:28It took this this representation which
140. 5:31used to be in one's complement -15 and
141. 5:33then all the ones was here. We didn't
142. 5:35want that. We wanted to bring it back
143. 5:37one more. So that's why
144. 5:41that term that top level term -6 pulls
145. 5:43that down so that this is the -6 pulling
146. 5:46that value down to -6. If I then stretch
147. 5:4916 more guys or 15 16 more guys there
148. 5:52this will end up at minus one right -6
149. 5:54to minus1 is 16 things. So that's why
150. 5:57that works that cool that cool top level
151. 5:59term this cool top level term it's
152. 6:01because you grabbed that negative guy
153. 6:03that smallest negative number and pulled
154. 6:06it over by exactly one in one's comp was
155. 6:08-5 and now it's -6 which is why why it
156. 6:11works. So, let's look at our odometer
157. 6:14now. And let's see if our we have it.
158. 6:15Let's see if our overlap here. Ready?
159. 6:17There we go. There's 0 to 15. And no
160. 6:21overlap. And as I said before, all ones
161. 6:24is negative one. Huh? With the thing.
162. 6:27And then there's all ones negative 1.
163. 6:30Love it. Okay.
164. 6:32Two to the n minus one non- negatives.
165. 6:34Two to the n minus one negatives. One
166. 6:36zero. Okay. How many positives? Ask
167. 6:39yourself that. And then we'll see this
168. 6:41next encoding.