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

1. `sizeof(&m)`
2. `-1`
3. `m & -m`
4. `m + ~m + 1`
5. `16 >> 2`
6. `m & ~m`
7. `m`
8. `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):

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);
}
}```

D

QUESTION 5C.

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

J

#### 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
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?

1. Array
2. Array of pointers to arrays
4. 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.

1. `char`
2. `int`
3. `unsigned long`
4. `unsigned long long`
5. `char *`
6. None of the above

`int`, `unsigned long`, `char *`