It is relatively easy to convert positive integer numbers to binary and
vice verso. Negative numbers can also be represented. There has been
more than one system used for this.
Sign magnitudeSign magnitude is where a binary number is indicated to be negative by putting a 1 in its leftmost position. Incidentally, this is called the most significant bit as it has the highest value. Old computer systems used to use this system. However, it has some weaknesses. Using this system and 8 bits -7 is represented by
The biggest negative number is -127 - (64+32+16+8+4+2+1 = 127)
The biggest positive number is 127 (64+32+16+8+4+2+1 = 127)
Using this system there are two representations of zero: 10000000 and 00000000. Also, ordinary binary addition does not work. For example, in a 4 bit system, adding 3 and -2 gives an erroneous result
Computers using this representation had to use a different algorithm for addition. One's and two's complementOne's complementTo deal with the addition of a positive and negative number problem the one's complement system was created. It has a basis in Mathematics but that will not be explored here. The negative or complement of a number is its digits flipped. Ones become zeros and zeros become ones. For example, using a 4 bit system, 2 or 0010 becomes -2 or 1101. Addition can be done similarly to ordinary binary addition with one change: any carry from the left-most digit has to be added to the right-most digit. For example 4 + -2 is
So, subtraction can be done using one's complement by finding the complement of the positive version of the subtracting number, then adding it to the positive number. Issues with one's complement There are two issues with one's complement.
Two's complement For a definition visit this Wikipedia page Also see the section that this page points to: more detailed explanation with examples The two's complement system was invented to fix the above issues. To find the complement of a number first flip the digits and then add 1 to the right-most one. For example, in a 4 bit system, to get -2 1) Flip: 0010 (2) => 1101 2) Add 1 => 1110
Now adding 4 and -2 (or subtracting 2 from 4) becomes
Note: That if there is a 1 carry left over it has to be discarded to get the correct answer. How about adding -4 and 2 (or subtracting 4 from 2)? 4 = 0100, flipped => 1011, add 1 => 1100.
The result looks like it should be 14. This is plainly wrong. So what do we do? Now is the time to talk about how negative numbers are represented. Representing Negative Numbers: the signed number system
In the decimal system integers can be negative or positive. Number
systems where this is so are called signed. Wholly positive systems are
said to be unsigned, whereas those that include negative values are
said to be signed. Binary number systems can be signed or unsigned too.
For a system using a given number of bits the number of values that can
be represented is 2n
where n is the number of bits. However, if the system is signed then
allowance has to be made for negative values and this limits the
possible largest negative and positive numbers to approximately half of
the possible largest unsigned value. Because 0 is included in the
positive range the largest positive number is 2n-1 - 1, whereas the largest possible negative number is -2n-1.
For example, using 8 bits the number of possible values is 2 8 or 256. If the system is positive (or unsigned) then the values 0 to 255 can be represented. If the system is signed then 256 values can be again represented, but this time the ranges are -128 (-27) to -1 (128 numbers) and 0 to 127 (27 - 1) (128 numbers). The way a negative integer is represented using a bit pattern in a signed system is by making the value of the left-most bit a 1. Furthermore the decimal value of this bit is the negative of what it is in an unsigned system. An example using 4 bits will help. Note that the leftmost bit in an unsigned system would normally have a value of 8. In a signed system its value is -8.
So the signed binary number 1111 has a decimal value of -8 + 4 + 2 + 1 = -1. In fact, this bit pattern gives the most positive negative value using a 4 bit system. The most negative is the pattern 1000 => -8. Using a signed binary number system positive numbers always have a 0 in the left-most bit. Here is an example.
0101 = 4 + 1 = 5. The bit pattern that gives the most positive value using a 4 bit system is 0111 => 7. Zero is represented by the pattern 0000. Note how the range of positive numbers is basically halved (as explained in the grey box above) and is 0 to 7. The negative range is -8 to -1. SO getting back to the problem when we added 2 and -4 and got 1110 we can now say that because we are dealing with negative numbers (-4 is negative) we are automatically using the signed system and the answer can be worked out quite simply: 1110 = -8 + 4 + 2 = -8 + 6 = -2 (this is correct). It is important to note that the same answer can be gained by finding the two's complement of 1110, converting it to a decimal and negating that value: 1110 flipped => 0001, add 1 => 0010 => 2, 2 x -1 => -2 (correct). This is a perhaps the simplest system.
The rule of thumb is that if the result of adding numbers, where
one or both of them are negative, has a 1 as its left-most digit then
take its two's complement to find its positive representation, then
negate it.
OverflowIt is possible to get an incorrect result when doing two's complement arithmetic. For example, add -100 to -63. The answer should be -163. Let's see if it is.Using 8 bits 100 => 01100100, flip it => 10011011, add 1 => 10011100. Therefore 10011100 is -100 in two's complement. And, 63 => 00111111, flip it => 11000000, add 1 => 11000001. Therefore 11000001 is -63 in two's complement.
As can be seen the result, if true, is a positive number as the left-most digit is a zero. However, the answer 93 is not correct. It should be -163. If we were able to use an extra digit on the left our result would be correct as 101011101 is negative and using the rule of thumb method above gives an answer of -163. However, as mentioned before, if a system is fixed, say at a maximum of eight bits, then an overflow occurs and the answer is wrong. Whether an overflow has occurred or not can be seen from the pattern of the carry into and carry out bits for the left-most digit (the ones in bold green). If they do not match then an overflow has occurred. In the example above the carry bits are 1 and 0, which do not match. If the carry bits are 0 and 0 or 1 and 1 then the answer is correct, as when -4 was added to 2. Additional resourcesThe following links point to a more in depth look at Two's complement. |