How would you store integers as bits? If you only care about unsigned integers, also known as nonnegative integers, then it’s easy: just store binary representations. For example, 37 has the representation 100101 because . Negative integers are usually handled with a method called “two’s complement”, which seemed pretty obscure when I first learned it. But this method is actually inevitable: given enough time, you could have invented it yourself. I will explain why in this post.
Storage
For simplicity, imagine you are tasked with representing integers using only eight bits, a byte if you will. That gets you different bit patterns. Using the binary representation method above, you can represent all integers from 0 to 255. But if you care about negative integers too, you need a more even split.
First attempt: sign bit
This is your first thought: use one of your eight bits to indicate whether the number is supposed to be positive or negative, and the remaining seven bits will be the usual binary representation. The first bit is set aside for this task, with zero indicating positive, and one indicating negative. So, for example, 37 would have a binary representation 00100101, while -37 would be 10100101. This has the advantage of unsigned compatibility: 37 signed and 37 unsigned have the same representation.
Now you can represent all positive integers whose binary representation fits into 7 bits, and their negative counterparts, and zero. Spelling that out, we get to represent all integers from -127 to 127.
Sign bits work fine, but there are a couple of issues keeping them away from the perfection of two’s complement.
Issues
First, notice that there are only 255 integers from -127 to 127, while we were supposed to get 256 different integers; where has that missing number gone? The problem is that zero is double counted: we have a positive zero 00000000 and a negative zero 10000000. This is wasteful, inelegant, and will cause some headaches when programmers try to compare integers to zero.
Second—and this is a more subtle problem—it’s hard to do arithmetic with this representation. Simplifying a tad, all arithmetic in your computer is done by a circuit called the ALU (arithmetic logic unit). The ALU only has a few operations builtin, but it does those pretty fast. One of those operations is addition, performed much like we learned in school, but in binary rather than decimal numbers. Here a simple sum of the type the ALU has to deal with.
|||
100110 = 38
+ 001111 = 15
--------
110101 = 53
This works great if our integers are unsigned. Unfortunately, the sign bit does not play nice with addition. For example, let’s see what the ALU would do when asked to add 37 to -37, using the representations we had earlier.
| | |
00100101 = 37
+ 10100101 = -37
----------
11001010 = -74
According to the ALU, the sum is -74; less than ideal. To get the right answer, we would have to soldier an special circuit for signed arithmetic in the ALU chip, which is already crowded. For example, you could install a “substraction” operator and instruct the ALU to do case-by-case analysis on the sign bit. This is undesirable, but at this point it is not clear that we can do any better.
Desiderata
In our discussion of the sign bit, we have identified three desiderata for a signed integer representation:
- Unsigned compatibility
-
If n is a positive integer, then n as an unsigned integer and n as a signed integer should have the same bit representation (up to leading zeros). This makes unsigned to signed conversions cheap. It’s also one less thing the ALU has to remember.
- Non-redundancy
-
We should make the most of the available bits we have. For eight bits, we want to be able to represent 256 different numbers, while the signed bit representation only allows 255 different numbers, since zero has two representations.
- ALU arithmetic
-
We want to make the most of the builtin operations the ALU has; as much as possible, we shouldn’t require special circuits in the ALU to handle our new representation. This seems like an elusive goal, yet we can get a nice result with the method of the complements.
Second attempt: ones’ complement
As I’ve hinted already, there is a nice trick to get the ALU’s builtin unsigned addition to work with signed integers. It’s like the sign bit method, but instead of flipping only the leading bit to negate a number you flip all bits. So, for example, while 37 still has the representation 00100101, -37 now has 11011010. Both 00000000 and 11111111 represent zero, so that n and always add up to zero using ALU arithmetic:
00100101 = 37
+ 11011010 = -37
----------
11111111 = 0
In fact, all sums work as expected (there is a small problem with overflow but we won’t touch upon that here). There is still the problem of redundancy, but ones’ complement is a great improvement over the sign bit method.
Third attempt: two’s complement
The sign bit method is quite natural, and ones’ complement is also perhaps a natural extension if you sit down to think about the problem. To motivate two’s complement, I will present these methods from a different perspective.
Imagine listing all 256 different bit patterns in the usual lexicographical order. Ignoring the leading zeros, the list would start with 0,1,01,10,11,100, etc. Our problem is basically to assign an integer to each item in this list. The unsigned compatibility desideratum implies that the first 128 bit patterns are to be interpreted as usual binary numbers. That leaves the second half of the list for negative integers.
The sign bit method basically “shifts” the magnitude assignments of the first half onto the second half. In the picture below, I have indicated both the positive and negative zeroes with a vertical bar.
256 bit patterns
|>>>>>>>>>>>>>>>>|>>>>>>>>>>>>>>>>
0 positive 0 negative
The ones’ complement method “shifts and reverses” the magnitude assignments:
256 bit patterns
|>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<|
0 positive negative 0
It is clear now why 00000000 and 11111111 are both zero in this picture.
The two’s complement method comes from the observation that, starting with one’s complement, we can get rid of the negative zero, and claim space for an additional negative integer, if we shift magnitudes further by one slot at the very end:
256 bit patterns
|>>>>>>>>>>>>>>>>*<<<<<<<<<<<<<<<<
0 ^
extra negative integer
More concretely, to negate an integer we flip all bits and add 1. In our usual example:
||||||||
00100101 = 37
+ 11011011 = -37
----------
00000000 = 0
Note that the last carry falls out of range and is ignored. All the sums work out correctly, though we won’t prove that here. Also negating zero yields the same zero. And we can represent all integers from -128 to 127, more than before. What more could you ask?
Implementation
Here is a small implementation of two’s complement in C, to illustrate the ideas talked about in this post.
#include <limits.h>
#include <assert.h>
typedef unsigned TwosComplInt;
enum { BITS = CHAR_BIT * sizeof(TwosComplInt)};
TwosComplInt
twos_compl_int_negate(TwosComplInt x) {
/* flip and add one */
return 1 + ~x;
}
int
twos_compl_int_is_negative(TwosComplInt x) {
/* return leading bit */
return x >> (BITS - 1);
}
int
main() {
TwosComplInt zero = 0;
TwosComplInt thirty_seven = 37;
TwosComplInt negative_thirty_seven = twos_compl_int_negate(37);
assert(!twos_compl_int_is_negative(thirty_seven));
assert(twos_compl_int_is_negative(negative_thirty_seven));
assert(thirty_seven + negative_thirty_seven == zero);
return 0;
}
We haven’t talked about multiplication: that will have to wait for a future post.