No more secrets Part 8: More or Less? A trick to process signed numbers
At a first sight our row of adders seems to be able to perform the sum operation only on natural numbers (or more precisely a finite initial subset of the naturals including zero, as naturals are infinite). I mean, how can we process negative numbers? Do we need a specific circuit?
The answer is "almost not". The same circuit is able to process positive and negative numbers. Here the trick is build in mathematics rather than electronics. Only a small specific circuit will be needed to compute whether the computation generates an overflow or not.
We will consider half of the numbers as positive (or zero) and half as negative. If we consider a suitable sorting sequence of the binary configurations, the row of chained adders is already able to manage both positive and negative numbers.
The 'suitable sequence' id the following one.
- all the numbers whose most significant bit (MBS) is zero are positive or zero and have the same encoding of the natural numbers, so a number whose MSB is zero and all the other bits are one is the maximum positive number
allowed in this encoding.
- all the numbers whose MSB is one are negative are negative. The number having all its bits set to one is -1, the previous number (all one but the last bit) is -2 and so on up to (in this case it should be better to say 'down to') the number having all the bits valued zero.
The following table shows the encoding for signed integer number under the educational hypothesis of three or four bit wide numbers. Three bits permit to encode numbers in the range -4, +3, the range of a four bit integer is -8, +7. In the real world integers are 16, 32, 64 or even 128 bit wide. A 16 bit integer encode numbers in the range -32768, +32767, a 32 bit integer range is: -2147483648, +2147483647. It is useless to print here the ranges for larger integers, they are just very long numbers. The basic point is that the idea presented here is exactly the same used in the real Arithmetic and Logic Units (ALU) in the processors (CPU) of our computer. The only difference is the number of bits.
3bits unsigned signed 4bits unsigned signed
000 0 0 0000 0 0
001 1 1 0001 1 1
010 2 2 0010 2 2
011 3 3 0011 3 3
100 4 -4 0100 4 4
101 5 -3 0101 5 5
110 6 -2 0110 6 6
111 7 -1 0111 7 7
1000 8 -8
1001 9 -7
1010 10 -6
1011 11 -5
1100 12 -4
1101 13 -3
1110 14 -2
1111 15 -1
This encoding has several nice properties.
From the table it is possible to see that all the numbers in the three bit encoding have the same representation when encoded using four bits if we take into consideration only the three least significant bits. If we want to convert a number encoded as 4-bit integer in one encoded as 3-bit integer, it is sufficient to delete the MSB. If the number has in the range allowed for a 3-bit number the resulting number represents the same value. The conversion of a 3-bit integer to a 4-bit integer is always possible but it is a bit trickier: the missing MSB of the 4-bit encoding must have the same value of the MSB of the 3-bit encoding.
010 -> 0010 101 -> 1101
In general to convert an n-bit integer into an m-bit integer:
- if n>m: delete n-m leading bits, if the original number is in the
range of an m-bits encoding both encodings represent the same number. (the n-bit encoding should have n-m+1 leading bits having the same value, i.e. n-m+1 leading zero bits or n-m+1 leading one bits)
- if n<m: copy the n bits of the n-bit encoding in the final, right-hand
side of the m-bit result. Set all the remaining bits of the results as copies of the MSB/sign bit of the n-bit configuration.
Examples: conversion 8->4 bit: 00000110 is 6 -> 0110 is 6 (it is possible, it begins by five zeros) 11111011 is -5 -> 1011 is -5 (this time there are five ones) 00011000 is 24 the truncation gives a wrong result, 24 is not representable in the range of a 4-bit integer, in fact there are ones and zeroes in the first five bits of the number). conversion 4->8 bits: 0100 is 4 -> 00000100 is 4 1110 is -2 -> 11111110 is -2
The most important property of this encoding for negative numbers is that we can sum unsigned and signed integers using the same circuit (provided we do not take into account the final carry).
Let us try some sums using 4-bit signed numbers:
4 + 2 -> 0100 + 0010 = 0110 -> 6 6 + (-2) -> 0110 + 1110 = (1)0100 -> 4 (-2) + (-3) -> 1110 + 1101 = (1)1011 -> -5 (-3) + 6 -> 1101 + 0110 = (1)0011 -> 3
So, we don't need a different circuit to sum relative numbers, if we choose this smart encoding for the negatives. The same circuit does the same work, we just change the interpretation, i.e. the meaning we give to each configuration of bits.
For the sake of completeness, there is one difference. The detection of the overflow should be computed in a different way. By the way, an overflow occurs when the result of a cumputation exceeds the range of the representation for the number of bits provided for the result.
For unsigned integers an overflow occurs when the carry generated by the adder of the MSB bit is one. This is not the case for relative numbers, as we have seen in the examples above that the MSB carry can be generated, in three out of four example there has been a carry but all the results are correct, no overflow occured.
The general rule is that there is an overflow of the sum between signed numbers when (and only if) the XOR between the Cin and Cout bit of the MSB is one.
It might be clearer using an example:
4 + 2 -> 0100 + 0010 = 0110 (Cout = 0)
100 + 010 = 110 (Cin = 0) 0 XOR 0 = 0 no overflow
6 + (-2) -> 0110 + 1110 = (1)0100 (Cout = 1)
110 + 110 = (1)100 (Cin = 1) 1 XOR 1 = 0 no overflow
(-2) + (-3) -> 1110 + 1101 = (1)1011 (Cout = 1)
110 + 101 = (1)011 (Cout = 1) 1 XOR 1 = 0 no overflow
(-3) + 6 -> 1101 + 0110 = (1)0011 (Cout = 1)
101 + 110 = (1)011 (Cout = 1) 1 XOR 1 = 0 no overflow
In fact these example are the same, and the results are correct.
6 + 4 -> 0110 + 0100 = 1010 (Cout = 0)
110 + 0100 = (1)010 (Cin = 1) 0 XOR 1 = 1 overflow
in fact ten, the result is beyond the range of representation for a 4-bit
signed integer.
-7 + (-5) -> 1001 + 1011 = (1)0100 (Cout = 1)
001 + 011 = (0)100 (Cin = 0) 1 XOR 0 = 1 overflow.
-12 is not representable either.