CS61C Spring 1999
Section 23 TA: Gek Siong Low (cs61c-tb)
Week 4 Discussion notes
Announcement
I've uploaded spim 4 to the class webpage, so there should not be any more inconsistencies between the home version and the lab version.
Number Representation - Two's complement
From the survey, it seems that most of you already know two's complement, so I'll just do a "quick" review of the topic here.
Before we start going into the details of two's complement representation, I want to point out that two's complement is NOT the same as negative binary numbers. It is simply a way to represent negative numbers with a finite number of bits. You can get through this class without making this distinction, but I want to make this distinction clear. This will become even clearer when we start talking about floating point representation.
What is a number? Basically, we have a sign (+/-), some digits, and a fractional part (to be discussed later). We use a finite number of symbols to represent each digit. This B number of symbols is called the base. For an ordinary number, there is no limit on the number of digits, i.e. the number can be as negative or positive as you want.
The problem with computers is that we can only hold a finite number of digits. There are two possible symbols (0 or 1) for each digit, called a bit. So for n bits, we can represent a total of 2^n bit strings. Note that I didn't say that these 2^n "numbers" have to be equally spaced. This will be made clear when we do floating point representation.
Unsigned Integers
The easiest way to allocate these 2^n bit strings would be to just enumerate them from 0 to 2^n. However, you cannot represent negative numbers with this scheme.
Two's complement
The problem in representing negative numbers is which bit strings should we define as negative? The best solution would be one where there is no ambiguity in representation and easy to perform arithmetic operations on. Several schemes have been tried (I'll tell you about them if you are interested) but the most common one in use today is two's complement representation.
One way which I find it useful for visualize two's complement is to arrange the 2^n bit strings in a circle. We know that half of the bit strings on the left begins with '0' and the other half on the right begins with '1'. We place our number line around this circle, centered around zero. The 2^(n-1) numbers on the left are the positive numbers, which are just what we'll get if we enumerate the numbers starting from zero. The 2^(n-1) numbers on the right are our negative numbers. Note also that because we divide the 2^n bit strings in this way, we can identify a number as positive/negative by looking at the first bit (which we call the sign bit, not to be confused with the +/- in ordinary numbers).
What is the range of numbers we can represent with two's complement? The circle is almost symmetrical. Because we need a slot on the left for the number zero, we can represent one more negative number than positive number (excluding zero). Hence, the range of two's complement representation for n bits is from -2^(n-1) to 2^(n-1)-1. For example, for a 16 bit representation, we can represent numbers from -32768 to +32767.
Going anti-clockwise:
|
|
00...000 | 11...111 = -1
|
00...001 | 11...110 = -2
|
|
|
|
|
|
|
|
|
|
01...110 | 10...001
|
01...111 | 10...000
|
|
2^(n-1) numbers on the left | 2^(n-1) numbers on the right
|
+ve | -ve
Converting between negative and positive numbers
Note that the bit strings on the left are complements (hence two's complement) of the bit strings on the right, but the numbers they represent are offset by one position. This illustrates how to convert between positive and negative numbers in two's complement:
1. Take the complement of the number (flip the bits) 2. Add 1
In the lecture notes, there is a formula for converting two's complement to decimal. The observation gives us an easier alternative for converting a negative two's complement number to decimal.
Example: (n=4)
Using formula Using above method
1100 (base 2) = -2^3 + 2^2 + 0 + 0 Flip bits: -> 0011 (base 2) = 3 (base 10)
= -8 + 4 Thus, 1100 (base 2) = -(3+1)
= -4 (base 10) = -4 (base 10)
Why two's complement?
I'm not going to confuse you with other schemes for representing integers. I'll just say that the most important reason for using two's complement is that there is only one representation for 0 and therefore there is no ambiguity. Secondly, we don't have to deal with special cases, which makes it easy to implement the arithmetic operations in hardware.
ANDs, ORs, and shifts
These are all bitwise operators, which means that they work on the bit strings themselves. Do not confuse AND/OR with the logical operators.
1. AND (& in C)
The AND operation is used to mask out or to unset certain bits in a bit string. The important property here is that: x AND 0 = 0, and x AND 1 = x. Masking allows us to extract specific bits from a bit string.
Example: 1110001001010100001011010101000100
mask 0000000000000000011111111111111100
result 0000000000000000001011010101000100
---------------
2. OR (| in C)
The OR operation is used to set certain bits of a bit string. The important property here is that: x OR 1 = 1, and x OR 0 = x.
Example: want to set bits 9, 14 and 16
1110001001010100001011010101000100
OR with 0000000000000000010100001000000000 (start counting from 0)
result 1110001001010100011111011101000100
- - -
Truth tables: x y AND OR
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 1
Shifts
There are left shifts and there are right shifts. Shifting the bits left shifts out the leftmost bit and inserts a zero at the right end. Shifting left by one bit has the same effect as multiply an integer by 2.
For right shifts, the picture is slightly complicated. There are two types of right shifts: arithmetic and logical. For arithmetic right shift, the bit inserted in the left is the same as the sign bit, so a negative integer remains negative and a positive integer remains positive. An arithmetic shift right is the same as integer division by 2. Logical shifts pads in zeros on the left, and are usually what we want when we perform shifting and masking of bit strings. In MIPs we have different instructions for these two types of shifts: srl and sra.
In C, however, all we have are the '>>' operators for right shifts. The point to note here is that the C specs let the right shifts for signed integers to be machine-dependent, so you don't really know if it's a logical or arithmetic shift! Most compilers between platforms agree on the actual operation performed, but you should not assume that. In project 2, since what we want are logical shifts, you can ensure logical shifts by typecasting your variables as unsigned integers.
Branches and Jumps
Just a few reminders about branches and jumps in MIPS since you'll be dealing with them in the second project.
1. Branches
The target address in the instruction is a word-address. So remember to multiply by 4 to get the
correct byte address. Note also that the PC in reality is already pointing to the next instruction,
so you must add 4 to the result, because the branch is relative to (PC+4) in reality.
The formula is thus: branch address = PC + 4 + 4*(branch target in instruction)
2. Jumps
The target address in the jump field is also a word-address, so you have to multiply by 4 as well.
However, there is a subtlety here. The jump target is supposed to an absolute address, but we've only
accounted for 26+2=28 bits (26 for the targt field and 2 for the multiply by 4). What about the last
4 bits? The missing 4 bits comes from the top/leftmost 4 bits in the PC, and you should put
that in for correctness.
Written by : Gek Siong Low (cs61c-tb), Spring 1999