Binary Signed Integers – Ones Complement

Binary Numbers In the last post, we saw that one of the major failings of the signed magnitude representation was that addition and subtraction could not be performed on the same hardware as for unsigned integers. As I pointed out, the reason for this is because negating a number in signed magnitude does not yield the additive inverse of that number. The ones complement representation eliminates this issue, although it does introduce new, subtle issues, and [spoiler] doesn’t address the problem of having two representations for zero.

Positive Signed Integers

Like in signed magnitude, the left-most bit denotes the sign of the integer: 0 for positive and 1 for negative. For positive integers, the remaining bits represent the magnitude of the integer, again like signed magnitude.

For a 4 bit integer, the non-negative numbers that may be represented are:

Binary	Decimal
0000	0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7

We see that we can represent 7 non-negative integers with a 4-bit, ones complement binary representation. The general rule is that a N-bit string can encode 0 through $2^{N-1}-1$ .

Addition and subtraction are straightforward, but we do need to be concerned about overflow. Overflow?

Overflow, also called binary overflow, occurs when the magnitude of the result of a mathematical operation on a binary number, in this case signed binary integers, exceeds the magnitude that can be represented by the available bits.

As illustrated in the table above, we see that that the largest signed integer that can be represented by 4 bits is 7. Let’s take a look at what happens when we add 1 to 7:

$\begin{tabular}{cccccc} & 0 & 1 & 1 & 1 & (7)\\ + & 0 & 0 & 0 & 1 & (1)\\ \cline{1-5} & 1 & 0 & 0 & 0 & & \\ \end{tabular}$

If this were unsigned addition, that result would be just what we are looking for: 8. BUT this is signed addition, the 1 in the left most bit does not represent $2^3$ but instead represents the sign of the sum, and as previously stated, a 1 means a negative integer. This happens every time two signed integers are added together and the magnitude of their sum exceeds the representation. So if two positive integers are added and the sign of the result is negative, then overflow has occurred. This is an error, and the result is invalid.

Negative Signed Integers

As I stated in the introduction, the ones complement representation tackles the problem with the signed magnitude representation that makes mathematical operations on positive and negative integers difficult. With ones complement, negation of an integer does yield its additive inverse. In other words, in ones complement, a number plus its negation equals zero as the case should be.

The ones complement representation of a negative number is determined by taking the bitwise complement of the positive integer with the same magnitude. The bitwise complement of a bit string is obtained by inverting – flipping from 0 to 1 or 1 to 0 – each bit. So -1 is found by taking the bitwise complement, denoted with the ~ operator, of +1.

$\sim{0001} = 1110$

Let’s do a quick check to verify that +1 + (-1) equals 0:

$\begin{tabular}{cccccc} & 0 & 0 & 0 & 1 & (+1)\\ + & 1 & 1 & 1 & 0 & (-1)\\ \cline{1-5} & 1 & 1 & 1 & 1 & & \\ \end{tabular}$

This result represents both good news and bad news. The good news is that 1111 is 0. The bad news is that 1111 is technically -0. Like signed magnitude, ones complement suffers from two representations of 0: +0, or 0000, and -0, or 1111.

Now we can expand our table to show all of the integers that can be represented with 4 bits:

Binary	Decimal
0000	+0
0001	1
0010	2
0011	3
0100	4
0101	5
0110	6
0111	7

Binary	Decimal
1111	-0
1110	-1
1101	-2
1100	-3
1011	-4
1010	-5
1001	-6
1000	-7

An N-bit binary string can encode $-(2^{N-1}-1)$ to $2^{N-1}-1$ .

Considering overflow again, we see that we have an unavoidable problem: when adding two negative numbers, not only do we need to be aware of overflow from the magnitude bits, but we will always have overflow from the sign bits. This is because the left most bit which represents the sign is always 1 for negative numbers. How we handle this overflow depends on the situation.

Let’s start with a simple case: -1 + (-1). We know that in our 4-bit representation the answer, -2, is valid since its magnitude, 2, does not exceed what we can represent. The fact that -2 is shown in the table above to be 1101 should have been another clue. Let’s see what it looks like:

$\begin{tabular}{ccccccc} & & 1 & 1 & 1 & 0 & (-1)\\ + & & 1 & 1 & 1 & 0 & (-1)\\ \cline{1-6} & 1 & 1 & 1 & 0 & 0 & & \\ \end{tabular}$

First, notice that the magnitude bits overflowed (carried) into the sign bit. Because the sign bits were both 1, the sign bit of the sum remained 1, so the sum is negative. For the sum of two negative numbers to be valid, this always must be the case. If the magnitude bits did not overflow into the sign bit, the sign of the sum would be zero (1 + 1 = 0). We will come back to this.

So, what do we do with the overflow? One option is to ignore it. If we do this, the sum is 1100, or -3. Close, but no cigar.

End Around Carry

The solution is to do what is called an “end around carry.” This means we take the overflow bit and add it back in to the left-most bit of the sum and continue carrying as necessary until a finally solution is obtained.

$\begin{tabular}{ccccccc} & & 1 & 1 & 1 & 0 & (-1)\\ + & & 1 & 1 & 1 & 0 & (-1)\\ \cline{1-6} & 1 & 1 & 1 & 0 & 0 &\\ + & & & & & 1 &\\ \cline{1-6} & & 1 & 1 & 0 & 1 & (-2)\\ \end{tabular}$

And there is -2, the answer we were looking for. But why does end around carry give us the correct answer? The reason has to do with modular addition. To see why, let’s consider the same binary addition problem we just did, but instead of signed integers, let’s treat the bit strings as unsigned integers.

$\begin{tabular}{ccccccc} & & 1 & 1 & 1 & 0 & (14)\\ + & & 1 & 1 & 1 & 0 & (14)\\ \cline{1-6} & \cancel{1} & 1 & 1 & 0 & 0 & (12) \\ \end{tabular}$

We expect the sum to be 28, but because we discard the overflow bit, we are left with 1100, or 12. The interesting fact here is that $28 \equiv 12 \mod{16}$ . This is because a 4 bit unsigned integer can represent 16 numbers: 0 to 15. In general, an N-bit unsigned integer can represent $2^N$ numbers, so if an arithmetic operation overflows into a value requiring greater than N bits, that value will always be congruent to the value of the first N bits modulo $2^N$ . To learn why this is the case please see my article “Unsigned Binary Integers and Internal Congruence.”

Going back to our original problem of -1 + -1, first as ones complement signed integers:

$\begin{tabular}{cccccc} & 1 & 1 & 1 & 0 & (-1)\\ + & 1 & 1 & 1 & 0 & (-1)\\ \cline{1-5} & 1 & 1 & 0 & 1 & (-2) \end{tabular}$

Leaving the binary representations unchanged, but considering the numbers themselves to be unsigned integers gives us:

$\begin{tabular}{cccccc} & 1 & 1 & 1 & 0 & (14)\\ + & 1 & 1 & 1 & 0 & (14)\\ \cline{1-5} & 1 & 1 & 0 & 1 & (13) \end{tabular}$

We know that the addition of these two binary numbers are correct if we consider them as ones complement signed integers, but because of the end around carry, the sum is not what we would’ve expected if they were signed integers. As I stated above, for unsigned integers we expect to get 12 since $28 \equiv 12 \mod{16}$ , but we got 13 instead. What gives?

The reason: arithmetic with 4 bit ones complement signed integers is done modulo 15 and not modulo 16 like for unsigned integers. The duplicate representations of zero restrict the number of numbers we can represent with 4 bits to 15 instead of the 16 that unsigned 4 bit integers can represent. In general, an N-bit ones complement signed integer can represent $-(2^{N-1}-1)$ to $2^{N-1}-1$ , and the end around carry is necessary to account for losing a representation to the double zeros.

Ones Complement Summary

Positive integers are represented the same as if they were unsigned.
Negative integers are formed by taking the bitwise complement of the positive integer with the same magnitude.
End around carry is necessary to compensate for having two representations of zero.
If the sum of two positive integers is negative, or if the sum of two negative integers is positive, overflow has occurred and the magnitude of the sum is too large to be represented by the available bits.