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.

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:

and then invert all its bits:

and then add 1 (or, equivalently, 00000001):

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:

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.