# CS2100 Computer Organisation Notes

P.S. The following information is based on various resources from the course CS2100 NUS, certain parts are adapted to include my comments and explanations for my better understanding & review. I will try to include source in relevant section as much as possible to honor the authors' work (Mainly Prof Aaron & Prof Colin & TA Alvin).

P.P.S Half way through the course, I decided to change the way I take notes and therefore the information contained here only cover the first few chapters of the module.

``// while-loopint readArray(int arr[], int limit) {    int index, input;    printf("Enter up to %d integers, terminating with a negative integer.\n", limit);    index = 0; // Must remember to initialize to zero    scanf("%d", &input);    while (input >= 0) {        arr[index] = input;        index++;        scanf("%d", &input);    }    return index; // Which is the actual array size}``
``// for-loopint readArray2(int arr[], int limit) {    int index, input;    printf("Enter up to %d integers, terminating with a negative integer.\n", limit);    for (index = 0; index < limit; index ++) {        if (arr[index] < 0) {            break;        }        scanf("%d", &arr[index]);    }    return index - 1; // Which is the actual array size}``
• Reverse Array
``// iterative while-loopvoid reverseArray(int arr[], int size) {    int left = 0, right = size - 1, temp;    while (left < right) {        temp = arr[left];        arr[left] = arr[right];        arr[right] = temp;        left++;        right--;    }}``
``// iteractive for-loopvoid reverseArray2(int arr[], int size) {    int start, temp, end = size - 1;    for (start = 0; start < size / 2; start++) {        temp = arr[start];        arr[start] = arr[end];        arr[end] = temp;        end--;    }}``
``// recursivevoid reverseArray3(int arr[], int size) {    reverseArrayRec(arr, 0, size - 1);}void reverseArrayRec(int arr[], int left, int right) {    int temp;    if (left < right) {        temp = arr[left];        arr[left] = arr[right];        arr[right] = temp;        reverseArrayRec(arr, left + 1, right - 1);    }}``
``// recursive C-style : from TA Alvin CS2100void reverseArray4(int arr[], int size) {    if (size <= 1) {        return;    } else {        temp = arr[0];        arr[0] = arr[size - 1];        arr[size - 1] = temp;        // Add 1 to array pointer => shift pointer by 4 bytes        // => move to next item in array, that is the new base        // => treat it as removing the front and back items,        // hence size - 2        reverseArray4(arr + 1, size - 2)    }}``

# Sign extension

When we want to represent an n-bit signed integer as an m bit signed integer, where m > n. We do this by copying the sign-bit of the n-bit signed m - n times to the left of the n-bit number to create an m-bit number.

To show that sign extension is value-preserving, we can simply check two cases:

• If the signed bit is 0, adding 0s to the left is similar to adding 0 to the right of a decimal point. It does not change the value.
• If the signed bit is 1, adding 1s to the left seems to change the value, but not really. This is because the newly added 1s to the right of the newly added signed bit increases the value while the signed bit decreases the value of the number. This effectively cancels out the changes in value. E.g. Focusing on the value that signed bit and the extended signed bit portion, original: 1001 => -2**3 = -8, extended: 111001 => -2**5 + 2**4 + 2**3 = -8

# Addition of two 1's complement number with decimal

• Sign extend or pad zero to the end so that they are of equal length.
• Invert all the bits for negative number to use addition.
• If there is a carry out, add 1 to the result.
• Check for overflow if the result is opposite sign of A and B.

# Converting decimal numbers to fixed-point binary

When doing the rounding

• 0.0000 is rounded to 0.000.
• 0.0001 is rounded to 0.001.

# Represent decimal value in IEEE 754 format

• When converting the 32 bits to Hexadecimal, make sure that the signed bit is also included.

# Bitwise operations

``a = 001010b = 101011a | b = 101011a & b = 001010a ^ b = 100001~a = 110101a << 2 = 101000 # equivalent to a *= 4a >> 2 = 001010 # equivalent to floor(b /= 4)``

``x ^ x = 0x ^ 0 = xa = 00110a = 00110a ^ a = 00000b = 00000c = 00110c ^ b = 00110``

# Swap without temporary variable, with bitwise operator

``void swap(int *a, int *b) {    *a = *a ^ *b    *b = *a ^ *b # equivalent to *a ^ *b ^ *b = *a    *a = *a ^ *b # equivalent to *a ^ *b ^ *a = *b}``

## Summary​

• andi/ori/xori use zero-extension to fill in upper 32 bits. The operation acts on all 32 bits.
``andi x, 1 = xandi x, 0 = 0ori x, 0 = xori x, 1 = 1nor x, 0 = ~xxor x, 1 = ~xxor x, 0 = x``

## Set bits 2, 8, 16 to 1 in b, a -> \$s0, b -> \$s1, c -> \$s2​

``# 16th bit is outside the range of immediate, which is only 0 - 15th bit# use intermediate registers for resultslui \$t0, 0b1                # this sets the 16th bitori \$t0, 0b0000000100000100 # this sets 0 - 15th bitor \$s1, \$s1, \$t0``

## Copy over bits 1, 3 of b into a​

``lui \$t1, 0b1111111111111111ori \$t1, t1, 0b1111111111110101and \$s0, \$s0, \$t1                 # clear the two bits from aandi \$t0, \$s1, 0b0000000000001010 # get the two bits from bor \$s0, \$s0, \$t0                  # copy the bits over``

## Make bits 2, 4 of c inverse of bits 1, 3 of b​

``xori \$t0, \$s1, 0b0000000000001010 # this invert and copyandi \$t0, \$t0, 0b0000000000001010 # clear everything elsesll \$t0, \$t0, 1                   # shift left to 2, 4lui \$t1, \$t1, 0b1111111111111111  # clear out 2, 4 of c, 3 steps, lui, ori, andori \$t1, \$t1, 0b1111111111101011and \$s2, \$s2, \$t1or \$s2, \$s2, \$t0                  # copy over to c``

# MIPS arithmetic

a -> \$s0 b -> \$s1 c -> \$s2 d -> \$s3

d = 6a + 3(b - 2c) d = 6a + 3b - 6c d = 3(2a + b - 2c) d = 3(2(a - c) + b)

``sub \$t0, \$s0, \$s2   # a - csll \$t0, \$t0, 1     # 2(a - c)add \$t0, \$t0, \$s1   # 2(a - c) + bsll \$s3, \$t0, 2     # 4(2(a - c) + b)sub \$s3, \$s3, \$t0   # 3(2(a - c) + b)``

# MIPS tracing

``add \$t0, \$s0, \$ zero    # make a copylui \$t1, 0x8000         # set t1 to 1 at MSB and 0 else wherelp: beq \$t0, \$zero, e   # if t0 == zero, exit    andi \$t2, \$t0, 1    # t2 left with LSB    beq \$t2, \$zero, s   # if t2 LSB == 0, s    xor \$s0, \$s0, \$t1   # invert MSBs:  srl \$t0, \$t0, 1     # discard LSB    j   lp              # loop backe:                      # exit``

# What happens when integer overflow in C

• int is 4 bytes (in sunfire), which is 4 x 8 = 32 bits
• the range is from -2,147,483,648 (-2^31) through +2,147,483,647(2^31 - 1)
• This range comes from 32 bits 2s complement representation,
• from 10000000000000000000000000000000 (smallest negative number)
• to 01111111111111111111111111111111 (largest positive number)
• when adding 1 to the largest positive number, it becomes the smallest negative number
• adding another 1 will make it 10000000000000000000000000000001,
• which is -2147483647, (literally add 1 to the decimal number)

# For an n-bit sign-and-magnitude representation, what is the range of values that can be represented?

• -(2^(n-1) - 1)
• 2^(n-1) - 1

# 1s Complement

• -x = 2^n - 1 - x (in decimal)
• -x = 2^n - 1 - x + 1 (in decimal)
• minus 1 because you want the largest possible values in that base

• -2^(n - 1)
• 2^(n-1) - 1