CLASS 11

Two's Complement.

A natural way to represent 4 million numbers using 32 bits is using simple positional notation. Let's say we have 32 bits in which to store an integer. If we store the number using base two, we can hold 2^32 different numbers. Since the first number is zero, the largest number is 2^32 - 1. So the range of numbers we can store in the natural manner is 0 .. 2^32-1. Is this a good model for the integers? Not really, it's a better model for the set of natural numbers, which we call unsigned integers. Normally we think of integers as including negative numbers.

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:

avoid the two-zero problem;
implement addition consistently regardless of the signs of the operands; and
implement subtraction using the addition units.

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 = -1

Can 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)

Other Examples:

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.

Binary Signed Subtraction

A simple formula for binary subtraction:
a-b = a + (2^n - 1 - b) + 1 ,
where r is the base and n is the number of digits in the register

Subtraction using 2's complement:

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.

Condition Codes

The condition codes when instructions are represented as 2's complement are as follows:

Z - when all bits are 0
N - most significant bit is 1
V - set when sign of minuend and subtrahend differ, and the result is same sign as the subtrahend

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

Shifting

There are three instructions in Sparc Architecture to implement shifting:

sll     reg, reg(imm.), reg     -   Shift left logical
srl     reg, reg(imm.), reg     -   Shift right logical
sra     reg, reg(imm.), reg     -   Shift right arithmetic

Logical shift - Shift left or right, with zero copied in the end.
Arithmetic shift - Left shift same, hence there is no separate instruction, but on a right shift, sign bit is copied into the most significant bit position.

Unsigned Arithmetic

In case of unsigned instructions, we don't have a sign bit.

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 = 0

There 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

Multiplication

I am not preparing any notes for Multiplication and division, we will cover them diretly from the Text. So please get your text for today's class. The pages are 109-114, and then pages 115-117 for the format and details of the mulscc instruction which is used to implement multiplication.

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

Division

Binary division is carried out similar to decimal devision, but use is made of the 2's complement method for subtraction. We are not going to be covering Binary Division in this course.

Equivalence of multiplication/division and shifting

A shift is the movement of bits "side-to-side" in a register. Shifts can be right or left, depending on the motion of the bits.

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, reg

The 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.