Complementary Questions
When we discussed binary in Week 0, we focused on non-negative numbers. Recall, for instance, that 0 in decimal is 00000000
in binary, 1 in decimal is 00000001
in binary, and 2 in decimal is 00000010
in binary, assuming you use a full byte (8 bits) to represent each number. But what about negative numbers? We humans, of course, simply prefix decimal digits with a minus sign (-) as needed. But computers, ultimately, must rely only on zeroes and ones, so perhaps the simplest solution for them is to use just a bit (e.g., the leftmost) to represent a number’s sign. And so a computer might represent -1 in decimal as 10000001
in binary and -2 in decimal as 10000010
in binary. Notice how those bytes are identical to those for 1 and 2, respectively, except for their leftmost bit, which is now 1
. This binary representation of negative numbers, otherwise known as "sign-magnitude," is nice and simple, but you, unfortunately, end up with two representations of zero, 00000000
and 10000000
. And sign-magnitude doesn’t quite lend itself to convenient arithmetic.
In decimal, for instance, 1 + -1 is, of course 0. But let’s do that same math in binary using sign-magnitude, below. Notice how we’ve carried a 1
when adding 1
and 1
, since 1
+ 1
is 10
in binary, just as 5 + 5 is 10 in decimal.
00000001
+ 10000001
==========
10000010
It would seem that this sum of 1 and -1, in decimal, is actually -2, since the leftmost bit of 10000010
is 1
and the remaining seven bits (i.e., 0000010
) represent 2! Well that’s just not right. It should be 0, of course!
And so computers instead tend to represent negative numbers using "two’s complement," which is just a bit (ha!) different. To determine the representation of a negative number using two’s complement, you first take its positive representation, invert all its bits (changing each 0
to a 1
and each 1
to a 0
), and then add 1
to that result. Similarly can you convert a negative number using two’s complement to its positive representation via those same steps in the same order.
Accordingly, to represent the number we know in decimal as -1, we would first start with 1:
00000001
and then invert all its bits:
11111110
and then add 1
(or, equivalently, 00000001
):
11111110
+ 00000001
==========
11111111
And so -1 in decimal is 11111111
in binary, using two’s complement. Conveniently, its leftmost bit is, as with sign-magnitude, 1
, which holds true for all negative numbers in two’s complement. And arithmetic now works as expected. Let’s calculate 1 + -1 again using two’s complement:
00000001
+ 11111111
==========
00000000
Provided you confine yourself to eight bits and discard any ninth bit (that might otherwise result from carrying a 1
), 1 + -1, in decimal, is indeed 00000000
in binary in two’s complement.
Cornell has some notes that offer other examples.
Answer the below in complementary.md
, each in no more than two sentences.
Questions
-
(1 point.) How would you represent the decimal number we know as -3 with one byte in binary using sign-magnitude?
-
(1 point.) How would you represent the decimal number we know as -3 with one byte in binary using two’s complement?
-
(2 points.) Back in 2014, PSY’s "Gangnam Style" reportedly broke YouTube’s code, per the screenshot below:
Notice the negative number of views (-2130754499). Even though Google later admitted it was a joke, it technically could have happened, had Google’s engineers not stayed atop the potential problem. Why might the value of a counter, like PSY’s views, potentially become negative?
-
(2 points.) Recall
overflow.c
from Week 1. Why did that program, when compiled and executed, not only print a negative number but, thereafter,0
indefinitely? -
(1 point.) Why, in your own words, did the Ariane 5 rocket’s first test flight fail on 4 June 1996 (at a cost of millions of dollars)?
Debrief
-
Which resources, if any, did you find helpful in answering this problem’s questions?
-
About how long, in minutes, did you spend on this problem’s questions?