2013/SampleMidtermExtraSolutions

From CS61
Jump to: navigation, search

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:

Hello-swap.gif

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

Hello-f0.gif   Hello-f7.gif   Hello-f2.gif   Hello-f3.gif   Hello-f4.gif
A B C D E
 
Hello-f5.gif   Hello-f6.gif   Hello-f1.gif   Hello-f8.gif   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);
   }
}

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

  1. Array
  2. Array of pointers to arrays
  3. Linked list
  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 *