Do Not Stress Out About These Sample Midterm Solutions

2. Expressions

QUESTION 2A. Here are eight expressions. Group the expressions into four pairs so that the two expressions in each pair have the same value, and each pair has a different value from every other pair. There is one unique answer that meets these constraints. m has the same type and value everywhere it appears (there’s one unique value for m that meets the problem’s constraints). Assume an x86 machine.

sizeof(&m)
-1
m & -m
m + ~m + 1
16 >> 2
m & ~m
m
1

1—5; 2—7; 3—8; 4—6

1—5 is easy. m + ~m + 1 == m + (-m) == 0, and m & ~m == 0, giving us 3—8. Now what about the others? m & -m is, as we know, either 0 or a power of 2. This eliminates -1, leaving either m or 1. If m & -m matched with m, then the remaining pair would be 1 and -1, which clearly doesn’t work. Thus m & -m matches with 1, and m == -1.

5. Hello program

Now that we have the image in memory, we can manipulate it using C. For example, here’s a function.

void swap(void) {
   for (int i = 0; i < 16; ++i)
      cute[i] = (cute[i] << 8) | (cute[i] >> 8);
}

Running swap produces the following image:

Shintaro has written several other functions. Here are some images (A is the original):

File:hello-f0.gif	File:hello-f7.gif	File:hello-f2.gif	File:hello-f3.gif	File:hello-f4.gif
A	B	C	D	E

File:hello-f5.gif	File:hello-f6.gif	File:hello-f1.gif	File:hello-f8.gif	File:hello-f9.gif
F	G	H	I	J

For each function, what image does that function create?

QUESTION 5A.

void f0() {
   for (int i = 0; i < 16; ++i)
      cute[i] = ~cute[i];
}

H. The code flips all bits in the input.

QUESTION 5B.

void f2() {
   for (int i = 0; i < 16; ++i) {
      cute[i] = ((cute[i] >> 1) & 0x5555) | ((cute[i] << 1) & 0xAAAA);
      cute[i] = ((cute[i] >> 2) & 0x3333) | ((cute[i] << 2) & 0xCCCC);
      cute[i] = ((cute[i] >> 4) & 0x0F0F) | ((cute[i] << 4) & 0xF0F0);
      cute[i] =  (cute[i] >> 8)           |  (cute[i] << 8);
   }
}

QUESTION 5C.

void f3() {
   char *x = (char *) cute;
   for (int i = 0; i < 16; ++i)
      x[2*i] = i;
}

For “fun”

The following programs generated the other images in “Hello program.” Can you match them with their images?

f3—I; f4—B; f5—C; f6—F; f7—G; f8—A; f9—E

void f3() {
   for (int i = 0; i < 16; ++i)
      cute[i] &= ~(7 << i);
}

void f4() {
   swap();
   for (int i = 0; i < 16; ++i)
      cute[i] <<= i/4;
   swap();
}

void f5() {
   for (int i = 0; i < 16; ++i)
      cute[i] = -1 * !!(cute[i] & 64);
}

void f6() {
   for (int i = 0; i < 16; ++i) {
      int tmp = cute[15-i];
      cute[15-i] = cute[i];
      cute[i] = tmp;
   }
}

void f7() {
   for (int i = 0; i < 16; ++i)
      cute[i] = cute[i] & -cute[i];
}

void f8() {
   for (int i = 0; i < 16; ++i)
      cute[i] ^= cute[i] ^ cute[i];
}

void f9() {
   for (int i = 0; i < 16; ++i)
      cute[i] = cute[i] ^ 4080;
}

8. Data structures

Here are four assembly functions, f1 through f4.

f1:
    movl    4(%esp), %eax
    movl    8(%esp), %ecx
    testl   %ecx, %ecx
    jle .L2
    xorl    %edx, %edx
.L3:
    movl    4(%eax), %eax
    incl    %edx
    cmpl    %ecx, %edx
    jne .L3
.L2:
    movl    (%edx), %eax
    ret

f2:
    movl    8(%esp), %edx
    leal    0(,%edx,4), %ecx
    movl    4(%esp), %eax
    movl    (%eax,%ecx), %eax
    addl    %ecx, %eax
    movl    (%eax), %eax
    ret

f3:
    pushl   %esi
    pushl   %ebx
    movl    12(%esp), %ecx
    movl    16(%esp), %esi
    movl    20(%esp), %eax
    testl   %esi, %esi
    jle .L9
    xorl    %edx, %edx
.L10:
    movl    %eax, %ebx
    andl    $1, %ebx
    movl    4(%ecx,%ebx,4), %ecx
    incl    %edx
    sarl    %eax
    cmpl    %esi, %edx
    jne .L10
.L9:
    movl    (%ecx), %eax
    popl    %ebx
    popl    %esi
    ret

f4:
    movl    8(%esp), %edx
    movl    4(%esp), %eax
    movl    (%eax,%edx,4), %eax
    ret

QUESTION 8A. Each function returns a value loaded from some data structure. Which function uses which data structure?

Array
Array of pointers to arrays
Linked list
Binary tree

Array—f4; Array of pointers to arrays—f2; Linked list—f1; Binary tree—f3

QUESTION 8B. The array data structure is an array of type T. Considering the code for the function that manipulates the array, which of the following types are likely possibilities for T? Circle all that apply.

char
int
unsigned long
unsigned long long
char *
None of the above

int`, `unsigned long`, `char *

NOTOC