This web page describes the 2's complement representation of signed numbers as an extension of the binary representation of numbers. This means that the representation, when there are no limits on the number of digits, represents non-negative numbers exactly the same as the binary representation. The representation has the advantage that the addition operation extends without modification to negative numbers.
In addition to the 2's complement representation, there is a 2's complement operation. When this operation is performed on a sequence of bits representing a number it transforms the bits into the representation of the negative of the number. Since hexadecimal is a compact and more convenient form of binary, the operation is described in hexadecimal.
Although the 2's complement representation is described in a way that allows an arbitrary number of digits, computers work with truncated fixed-length representations. For that reason, conversions from signed decimal to 2's complement and from 2's complement to signed decimal are described in terms of fixed-length representations.
The 2's complement representation of integers has the following objectives:
We can see how to meet these objectives by looking at two simple additions. The first determines how -1 must be represented. The second determines how other negative numbers must be represented. This defines the 2's complement operation.
With a representation of signed numbers that meets the above conditions we can use the same implementation for adding signed numbers as for unsigned numbers. Even better, with a simple modification the implementation can also do subtraction.
Addition in binary works the same way as addition in decimal except for carries. In binary a carry into the next column is needed when a column total is 2 or more. For example,
1 1 1 0 1 1 0 1 1 1 1 1 1 0 1
In the second column from the right the column sum is 2. This is 0 with a carry into the next column, shown in blue. In the third column from the right the column sum is 3. This is 1 with a carry into the next column.
The representation for negative one is suggested by a binary odometer. What happens when the odometer backs up from a display of all 0s? In decimal you would get all 9s. In binary you would get all 1s.
The following addition shows that negative one must be represented by all 1s if addition for negative numbers works the same as addition of non-negative numbers.
. . . 1 1 1 1 . . . 1 1 1 1 1 1 . . . 0 0 0 0 0
An even easier addition shows how the negatives of other numbers must be represented if addition of negative numbers is to work the same as addition of non-negative numbers. This addition adds two numbers whose corresponding bits are always different. That is, where one number has a 0 the other has a 1, and vice versa.
. . . 1 0 1 1 0 . . . 0 1 0 0 1 . . . 1 1 1 1 1
The operation of forming a new bit pattern by replacing 0s in an original bit pattern by 1s and replacing 1s by 0s is called the 1's complement operation or bitwise complement operation, and the new bit pattern is the 1's complement (or bitwise complement) of the original bit pattern. The above addition shows that adding a bit pattern to its 1's complement gives the bit pattern that represents -1.
We can define a closely related operation, the 2's complement operation as a combination of two operations:
Now if the 1's complement in the above addition is replaced by a 2's complement the 1 added in the 2's complement operation makes the total add up to all 0s, the representation of the number 0. This shows that the number represented by the 2's complement of a bit pattern must be the negative of the number represented by that bit pattern.
We can also see how the negative of a number should be represented by subtracting the number from the representation of -1.
. . . 1 1 1 1 1 . . . 1 0 1 1 0 . . . 0 1 0 0 1
There are two interesting things about this subtraction:
These two facts are useful for dealing with carries in an efficient way.
When the 2's complement operation is performed on a sequence of bits representing a number it transforms the bits into the representation of the negative of the number. If the operation is performed twice it gives the original number.
Since conversions are easier and more reliable in hexadecimal, it is useful to be able to to do the 2's complement operation in hexadecimal. Then conversions require only the following skills:
If the number of bits is a multiple of 4 then recognizing negative numbers in hexadecimal is easy: look at the high-order headecimal digit. If it is from 0 to 7 then the number is non-negative. If it is from 8 to F then the number is negative.
The following table shows how to do the one's complement step. The two hexadecimal digits in a row of the table are one's complements of each other. You can do a one's complement operation on a multi-digit hexadecimal number by converting each of the hexadecimal digit to its one's complement.
As noted above, the signed and unsigned m-bit representations are the same for representable non-negative integers. The equivalence of negation and the two's complement operation gives us a quick way of finding the m-bit two's complement representation of a negative integer: find the unsigned representation of its absolute value, then do a two's complement operation.
Conversion in this direction fails whenever the decimal number is outside the range -2m-1 to 2m-1 - 1.
For example, we will convert -355510 to a 16-bit 2's complement number. Since it is negative, we first convert 355510 to hexadecimal.
Reading the digits from right to left gives 355510 = DE316. As a 16-bit number this is 0DE316.
But we want the representation of -3555 so we need to perform a 2's complement operation on 0DE3. Its 1's complement is F21C. Adding 1 gives us the 2's complement F21D.
Summarizing, F21D is the 2's complement representation of -355510.
To convert a m-bit two's complement number to decimal, you first look at the sign bit (the high order bit). If it is 0 the the number is non-negative and the determination of the decimal value is just an unsigned conversion from binary (or hexadecimal) to decimal. If the sign bit is 1, then do a two's complement operation, convert as an unsigned number, and affix a negative sign.
Conversion in this direction never fails.
For an example we will convert the 16-bit 2's complement number F21D to decimal. Since the high-order digit is in the 8 to F range, F21D represents a negative number. Applying the 1's complement operation to F21D gives 0DE2. Adding 1 gives 0DE3, the 2's complement of F21D. This represents the negative of the number represented by F21D.
Then we convert 0DE3 to decimal. We can ignore the leading 0.
This tells us that 0DE316 = 355510. Then the 2's complement of 0DE3, F21D, represents -3555.
Computers generally use fixed length representations for numbers. For example, in C and C++, there are three types for signed integers: int (usually 32 bits), short (usually 16 bits), and char (8 bits). Recent compilers also support long long (64 bits).
At times, it is necessary to coerce a signed integer from one type to another, resulting in a change in the number of bits used to represent the number. When a signed integer is coerced from a larger length to a smaller length, high order (leftmost) bits are discarded. If any of the discarded bits are 1 then the coerced value is incorrect. Compilers will generally warn you of this possibility.
When a signed integer is coerced from a smaller length to a larger length the original bits are padded on the left with copies of the sign bit of the original number. This is called sign extension.