How can we encode negative numbers? Well, we could set aside one bit that indicates whether the number is negative or positive. Say we did this. Then we would have: negative: 0 .. 2^31-1 and positive: 0 .. 2^31-1. This is called signed integer notation. So we are close, except that we have a negative zero and a positive zero. Most computer designers don't like that (though some computers have been built with this scheme). It seems clear that if all bits are zero, the number should be zero, and if the sign bit is set the number should be negative. So what about 10...0? Hmmm. We have a slight problem here.
Another issue arises. We would like addition to work the same whether it involves two positive numbers, a positive and a negative, or two negative numbers. Clearly, adding +2 and -2 when they are in signed-integer notation does not yield 0.
It turns out that with a proper representation of negative numbers, we can:
The drawback is that the representation is rather strange (until you get used to it!)
What number should we add to 1, if we are want to get zero as the
result, and are willing to throw away the carry-out bit? Answer:
00..01 + 11..11 = 00..00
So we could call 1..11 "-1" since in that case 1 + (-1) = 0. Likewise,
00..10 + 11..10 = 00..00 so 11..10 is "-2".
So, looking at bit patterns and the numbers they represent:
00..00 = 0 00..01 = 1 00..10 = 2 ... 01..10 = 2^31-2 01..11 = 2^31-1 10..00 = -(2^31) 10..01 = -(2^31-1) ... 11..10 = -2 11..11 = -1Can you find a relationship between a number (say, 2) and its complement (-2)? Well, note that the logical bit-flip of -2 is 1. Likewise, of -3 is 2.
The subtraction of a binary number from a bit pattern of all 1's is the same as a logical inversion of all bits. So subtracting from all 1's is called one's complement. Two's complement is just one's complement plus one.
How do we convert from negative to positive, or vice versa? The simple rule of thumb is "flip the bits and add one". Memorize this. This representation for integers is called "two's complement".
Let's use examples in base 2^8 (explain about sign extension). What's the representation, one's complement, and two's complement of: 0, 64, -64, -127, 127?
Characteristic of two's complement is that a number that is larger than (2^31-1) appears to be negative. This is another example of overflow. In this case, ignoring overflow would mistake a negative number for a large positive one. Also, we could add two negative numbers and get an apparently positive one, another example of a bad overflow.
This is why there is a V flag in the processor. The V (overflow) flag is set whenever the result of the computation is too large (in absolute value) to be held by the register.
1's complement of a number b = (2^n - 1 - b )
e.g. 1's complement of 11 (when there are 4 bits, i.e. n = 4) :
11 = 1011 (in binary) One's complement = 16 - 1 - 11 = 4 = 0100 (binary)
Hence, we can see that the 1's complement of a number is another number with it's digits reversed, i.e , the digits are toggled (0 replaced by 1 and vice versa).
Similarly, 2's complement of a number b = (2^n - 1 - b ) + 1
e.g. 2's complement of 13 (when there are 4 bits i.e. n = 4),
13 = 1101 (in binary) Two's complement = 16 - 1 - 13 + 1 = 3 = 0011 (in binary)
Again assuming n = 4, 2's complement of 11(1011) is 5(0101) 2's complement of 7(0111) is 9(1001)
Thus, it can be seen that the 2's complement of a number is a number with the digits reversed, starting from the digit after the rightmost 1 (all to the right of the rightmost 1, including itself, remain unchanged).
Both 1's complement and 2's complement of a number can be used to perform subtraction.
2's complement of a number b is equal to (2^n - 1 - b ) + 1.
So, (a-b) can be written as : = a + (2's complement of b). e.g.
11 - 7 = (1011) - (0111) = (1011) + (2's complement of 0111) = 1011 + 1001 = 0100 (carry out is ignored) = 4 (decimal)But if no carry out, then the answer is negative, and is the 2's complement of the answer. e.g.
4 - 15 = (0100) - (1111) = (0100) + (2's complement of 1111) = 0100 + 0001 = 0101 As no carry out, the answer is 2's complement of the result, i.e. (2's complement of 0101) = 1011 = -11 (decimal).
Hence, 1's complement and 2's complement are quite similar...but which one is preferred???
Ans: 2's complement, as in that case, there is one less addition involved, and the logic for it is easier to implement.
The condition codes when instructions are represented as 2's complement are as follows:
Instruction Condition codes bl (N xor V) = 1 ble (Z or N xor V) = 1 be (Z = 1) bne (Z = 0) bge (N xor V) = 0 bg (Z or (N xor V) = 0
sll reg, reg(imm.), reg - Shift left logical srl reg, reg(imm.), reg - Shift right logical sra reg, reg(imm.), reg - Shift right arithmeticLogical shift - Shift left or right, with zero copied in the end.
e.g. with 4 bits, we can represent numbers from 0 (0000) thru 15 (1111).
In case of subtraction, we can assume an extra bit which might represent the sign.
e.g. For calculating 10 - 3 (assuming 4 bits) :
10 - 3 = 1010 - 0011 = 01010 - 00011 = 01010 + 2's complement of 00011 = 01010 + 11101 = 00111 = 7 (decimal)
Instruction Condition codes blu C = 1 bleu Z = 1 or C = 1 beu Z = 1 bneu Z = 0 bgeu C = 0 bgu Z = 0 and C = 0There are also a set of instructions that test individual condition codes:
Instruction Condition codes Synonym Instruction bneg N = 1 bpos N = 0 bz Z = 1 be bnz Z = 0 bne bvs V = 1 bvc V = 0 bcs C = 1 blu bcc C = 0 bgeu
Example of multiplication: Multiply 3 an 5 , 3 in %o2, 5 in %o0
mov 3, %o2 mov 5, %o0 mov %o0, %y (special register, initially holds multiplier, nop finally the lower part of the product) nop nop (three nop as it takes time to store in %Y) andcc %g0, %g0, %o1 ! partial product = 0, clear N & V mulscc %o1, %o2, %o1 ! 32 times this instruction mulscc %o1, %g0, %o1 ! final shift mov %y, %o0
What do we do to the value of a number if we shift its representation left one place? All the bits occupy positions with one-higher place value, so the number has been multiplied by 2. What about if we shift it left 3 places?
The instruction is called sll, for shift left logical.
sll reg, reg_or_imm, regThe largest shift possible is 31.
What are the dangers of using sll for multiplication? What if we sll an integer that is greater than 2^30-1 ? And what about negative numbers?
Note: shift instructions do not modify the condition codes. You are on adjust: Command not found. OK, if left-shifting is equivalent (dangerously!) to multiplication by a power of two, what is the effect of right-shifting? Consider first positive numbers. Obviously, division. In fact, a trucating integer division by 2. What about for negative numbers? Doesn't work at all, but this time we have a solution: sign extension.
Sign extension means the filling-in of high-order bits based on the sign bit. So we have two versions of the right shift: srl (logical) and sra (arithmetic). The arithmetic version performs sign extension. The logical version fills in with zeroes, like the sll instruction.