Algorithm3.4.2Negate an integer, \(x\text{,}\) in binary (compute 2's complement)
Take the complement of \(x\text{.}\) (Flip all the bits.)
Add \(1\) to the result.
When representing signed decimal integers we have to use one bit for the sign. We might be tempted to simply use the highest-order bit for this purpose. Let us say that 0 means ‘\(+\)’ and 1 means ‘\(-\)’. We will try adding \(+2\) and \(-2\text{:}\)
\(\binary{0010}\) | \(=\) | \(+2\) | |
\(\binary{1010}\) | \(=\) | \(-2\) | |
\(\binary{1100}\) | \(\ne\) | \(0\) |
The result, using our code, would give \(\binary{1100}_{2} = -4_{10}\text{,}\) which is arithmetically incorrect.
We should note here that the problem is the way in which the computer does addition—it performs binary addition on the bit patterns that in themselves have no inherent meaning. There are computers that use this particular code for storing signed decimal integers. They have a special “signed add” instruction. By the way, notice that such computers have both a \(+0\) and a \(-0\text{!}\)
Most computers, including the ARM, use another code for representing signed decimal integers—the two's complement code. To see how this code works, we start with an example using the decimal number system.
Say that you have a cassette player and wish to represent both positive and negative positions on the tape. It would make sense to somehow fast-forward the tape to its center and call that point “zero.” Many cassette players have a four decimal digit counter that represents tape position. The counter, of course, does not give actual tape position, but a “coded” representation of the tape position. Since we wish to call the center of the tape “zero,” we push the counter reset button to set it to \(0000\text{.}\)
Now, moving the tape forward—the positive direction—will cause the counter to increment. And moving the tape backward—the negative direction—will cause the counter to decrement. In particular, if we start at zero and move to “\(+1\)” the “code” on the tape counter will show \(0001\text{.}\) On the other hand, if we start at zero and move to “\(-1\)” the “code” on the tape counter will show \(9999\text{.}\)
We can use our tape code system to perform the arithmetic in the previous example, \((+2) + (-2)\text{:}\)
Move the tape to \((+2)\text{;}\) the counter shows \(0002\text{.}\)
Add \((-2)\) by decrementing the tape counter by two. The counter shows \(0000\text{,}\) which is \(0\) according to our code.
Next we will perform the same arithmetic starting with \((-2)\text{,}\) then adding \((+2)\text{:}\)
Move the tape to \((-2)\text{;}\) the counter shows \(9998\text{.}\)
Add \((+2)\) by incrementing the tape counter by two. The counter shows \(0000\text{,}\) but there is a carry (\(9998 + 2 = 0000\) with carry \(= 1\)). If we ignore the carry, the answer is correct.
This second example illustrates the principle:
When adding two signed integers in the two's complement code, carry is irrelevant.
The two's complement code uses this pattern for representing signed decimal integers in bit patterns. The correspondence between hexadecimal, binary, and signed decimal (in two's complement) for four-bit values is shown in Table 3.4.1.
One Hexadecimal | Four Binary | Signed |
Digit | Digits (bits) | Decimal |
\(\hex{8}\) | \(\binary{1000}\) | \(-8\) |
\(\hex{9}\) | \(\binary{1001}\) | \(-7\) |
\(\hex{a}\) | \(\binary{1010}\) | \(-6\) |
\(\hex{b}\) | \(\binary{1011}\) | \(-5\) |
\(\hex{c}\) | \(\binary{1100}\) | \(-4\) |
\(\hex{d}\) | \(\binary{1101}\) | \(-3\) |
\(\hex{e}\) | \(\binary{1110}\) | \(-2\) |
\(\hex{f}\) | \(\binary{1111}\) | \(-1\) |
\(\hex{0}\) | \(\binary{0000}\) | \(0\) |
\(\hex{1}\) | \(\binary{0001}\) | \(+1\) |
\(\hex{2}\) | \(\binary{0010}\) | \(+2\) |
\(\hex{3}\) | \(\binary{0011}\) | \(+3\) |
\(\hex{4}\) | \(\binary{0100}\) | \(+4\) |
\(\hex{5}\) | \(\binary{0101}\) | \(+5\) |
\(\hex{6}\) | \(\binary{0110}\) | \(+6\) |
\(\hex{7}\) | \(\binary{0111}\) | \(+7\) |
We make the following observations about Table 3.4.1:
The high-order bit of each positive number is \(0\text{,}\) and the high-order bit of each negative number is \(1\text{.}\)
Although changing the sign of (negating) a number is more complicated than simply changing the high-order bit, it is common to call the high-order bit the sign bit.
The code allows for one more negative number than positive numbers.
The range of integers, \(x\text{,}\) that can be represented in this code (with four bits) is
\begin{equation*} -8_{10} \leq x \leq +7_{10} \end{equation*}or
\begin{equation*} -2^{(4-1)} \leq x \leq +(2^{(4-1)} - 1) \end{equation*}The last observation can be generalized for \(n\) bits to:
\begin{equation} -2^{(n-1)} \leq x \leq +(2^{(n-1)} - 1) \tag{3.4.1} \end{equation}In the two's complement code, the negative of any \(n\)-bit integer, \(x\text{,}\) is defined as
\begin{equation} x + (-x) = 2^{n}\tag{3.4.2} \end{equation}Notice that \(2^{n}\) written in binary is \(1\) followed by \(n\) zeros. That is, it requires \(n+1\) bits to represent. Another way of saying this is,
In the n-bit two's complement code adding a number to its negative produces n zeros and carry.
We now derive a method for computing the negative of a number in the two's complement code. Solving Equation (3.4.2) for \(-x\text{,}\) we get:
\begin{equation} -x = 2^{n} -x \tag{3.4.3} \end{equation}Equation (3.4.3) may look odd to a mathematician. Keep in mind that \(x\) in this equation is restricted to \(n\) bits, while \(2^{n}\) has \(n + 1\) bits.
For example, if we wish to compute -123 in binary (in the two's complement code) in 8 bits, we perform the arithmetic:
\begin{equation} -123_{10} = \binary{100000000}_2 - \binary{01111011}_2 = \binary{10000101}_2 \tag{3.4.4} \end{equation}or in hexadecimal:
\begin{equation} -123_{10} = \hex{100}_{16} - \hex{7b}_{16} = \hex{85}_{16} \tag{3.4.5} \end{equation}This subtraction is error prone, so let us perform a few algebraic manipulations on Equation (3.4.3), which defines the negation operation. First, we subtract one from both sides:
\begin{gather} -x -1 = 2^{n} - x - 1\tag{3.4.6} \end{gather}Rearranging a little:
\begin{align} -x - 1 &= 2^{n} - 1 - x\notag\\ &= (2^{n} - 1) - x\tag{3.4.7} \end{align}or
\begin{align} -x &= ((2^{n} - 1) - x) + 1\tag{3.4.8} \end{align}Now, consider the quantity \((2^{n} - 1)\text{.}\) Since \(2^{n}\) is written in binary as one (\(\binary{1}\)) followed by \(n\) zeros, \((2^{n} - 1)\) is written as \(n\) ones. For example, for n = 8:
\begin{equation*} 2^{8} - 1 = \binary{11111111}_{2} \end{equation*}Thus, we can express the right-hand side of Equation (3.4.7) as
\begin{equation} 2^{n} - 1 - x = \binary{111} \ldots \binary{111}_2 - x\tag{3.4.9} \end{equation}where \(\binary{111} \ldots \binary{111}_{2}\) designates \(n\) ones.
You can see how easy the subtraction on the right-hand side of Equation (3.4.7) is if we consider the previous example of computing \(-123\) in binary in eight bits. Let \(x = 123\text{,}\) giving:
\begin{align*} (2^{n} - 1) - x &= \binary{11111111}_{2} - \binary{01111011}_{2}\\ &= \binary{10000100}_{2} \end{align*}or in hexadecimal:
\begin{align*} (2^{n} - 1) - x &= \hex{ff}_{16} - \hex{7b}_{16}\\ &= \hex{84}_{16} \end{align*}From Equation (3.4.8) we conclude that
\begin{align*} -123 &= \hex{84}_{16} + 1\\ &= \hex{85}_{16} \end{align*}This leads us to Algorithm 3.4.2 for negating any integer stored in the two's complement, \(n\)-bit code.
Take the complement of \(x\text{.}\) (Flip all the bits.)
Add \(1\) to the result.