If we are given an m-bit computer word B with bits bm-1, bm-2, ..., b0, we can interpret it as an unsigned number with value
unsigned(B) = bm-1*2m-1 + bm-2*2m-2 + ... + b0*20.
This gives us a representation for numbers from 0 to 2m - 1.
If we want to represent negative values as well, we can just change the sign of the high-order bit bm-1, giving a signed number with value
signed(B) = -bm-1*2m-1 + bm-2*2m-2 + ... + b0*20.
This is called the m-bit 2's complement interpretation of B.
With bm-1 = 0, we get representations for numbers from 0 to 2m-1 - 1. With bm-1 = 1, we get representations for numbers from -2m-1 to -2m-1 + (2m-1 - 1) = -1. Thus we have several important facts about the m-bit 2's complement representation.
The third fact tells you how to convert between a computer word with sign bit 0 and its 2's complement signed value, assuming you know how to convert between unsigned binary numbers and decimal. The fourth fact could be used to do the same when the sign bit is 1, but there is an alternative method described below that does not require that you remember powers of 2. The fifth fact can be used to determine when arithmetic with signed numbers fails.
The one's complement operation is important bitwise operation for computer words. It converts each 0 bit in the word to 1 and each 1 bit in the word to 0. This operation is closely related to the negation operation for numbers. To see this, look at the follwing sum where B' is the one's complement of B.
signed(B) + signed(B') + 1 =
-bm-1*2m-1 + bm-2*2m-2 + ... + b0*20 + -b'm-1*2m-1 + b'm-2*2m-2 + ... + b'0*20 + 1 =
-bm-1*2m-1 + -b'm-1*2m-1 + bm-2*2m-2 + b'm-2*2m-2 + ... + b0*20 + b'0*20 + 1 =
-2m-1 + 2m-2 + ... + 20 + 1 =
-2m-1 + 2m-1 - 1 + 1 = 0
The terms in the third line are just the terms in the second line, rearranged to bring together like powers of 2. Then the bis and the b'is drop out because one of them is always 0 and the other is always 1. The equality between the fourth and fifth lines follows from the formula for summing a geometric series.
The above formulas show that the negative of signed(B) is signed(B') + 1. To make computer arithmetic reflect our arithmetic with numbers, addition on computer words is defined so that
signed(B + C) = signed(B) + signed(C) Thus we can write
-signed(B) = signed(B' + 1)
The operation on the right-hand side - doing a one's complement and adding one - is called the two's complement operation (not to be confused with the two's complement number representation). It is the computer equivalent of negating a number.
There is one case where the two's complement operation fails to give us the same result as negation. This is to be expected when our computer operations use limited size words. Since the range of integers represented by an m-bit two's complement representation is from, -2m-1 to 2m-1 - 1, there is number, -2m-1, whose negative is not even representable. In this case, the add one step fails to work correctly.
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.
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.
Since conversions are easier and more reliable in hexadecimal, it is useful to be able to to do the two's complement operation in hexadecimal. To do this, you only need to be able to do the following:
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.
| hex | binary | decimal | hex | binary | decimal | |
|---|---|---|---|---|---|---|
| 0 | 0000 | 0 | F | 1111 | 15 | |
| 1 | 0001 | 1 | E | 1110 | 14 | |
| 2 | 0010 | 2 | D | 1101 | 13 | |
| 3 | 0011 | 3 | C | 1100 | 12 | |
| 4 | 0100 | 4 | B | 1011 | 11 | |
| 5 | 0101 | 5 | A | 1010 | 10 | |
| 6 | 0110 | 6 | 9 | 1001 | 9 | |
| 7 | 0111 | 7 | 8 | 1000 | 8 |
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 duscarded 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.