Assignment 8, due Jul 10
Part of
the homework for CS:2630, Summer 2018

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper at the start of class on the day indicated (Tuesday or Thursday). Exceptions will be made only by advance arrangement (excepting "acts of God"). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!
a) Which of the MULTIPLY routines from the notes is most similar to TIMESU? (0.3 points)
b) What difference is there, if any, between TIMESU and the most similar version of MULTIPLY? Ignore cosmetic differences such as labels, indenting, or comment text. (0.4 points)
c) What is the benefit of this difference, if any? (0.3 points)
int leftshift( int a, int b ) { while (b > 0) { a = a << 1; b = b  1; } return a; }
The above subroutine is far from optimal. Consider a call to leftshift(x,1000) on a computer with a 32bit word. After the first 32 iterations, a will not change, yet the loop will continue for hundreds of additional useless iterations.
Computer scientists are well known for looking for logarithmictime solutions instead of linear ones. The above code is linear, the time taken to shift n bits is proportional to n. A logarithmictime solution can be written that tests each bit of the shift count b, shifting a one place if b is odd, two places if the next bit is set, three places if the next bit, and so on.
a) Translate the C code given above into well commented SMAL Hawk code. Note that you should be able to solve this with just 6 machine instructions. (1 point)
b) Write SMAL Hawk code for a logarithmictime solution. Ignore the problem of shift counts greater than 31. Note that this can be solved with only 16 instructions, a return instruction plus 5 groups of 3 instructions, one group per bit of the shift count. (1 point)