Exercise[28]

Why?

This exercise has several important objectives:

• It provides practice reading a small piece of powerful code that makes use of several logical and bitwise operators common to Java and JavaScript.
• It demonstrates and provides exposure to a simple while loop.
• It introduces a technique for and provides practice with the act of mentally stepping through code and keeping track of values of variables as they change in order to comprehend the code.
• It introduces the curious and surprising useful technique of shifting and cycling bits.

JavaScript Code

The following JavaScript function performs a one bit cycle shift left of a number n:

function cycleShiftLeft(n) {
  var oneBitCycleShiftLeft; // result
  var MAX_MASK = 1 << 30; // constant limitation
  var nShiftedLeft = n << 1;
  var bitMask = 1;
  while (bitMask <= n && bitMask <= MAX_MASK) {
    bitMask = bitMask << 1;
  }
  oneBitCycleShiftLeft = (bitMask ^ nShiftedLeft) + 1;
  return oneBitCycleShiftLeft;
}

Tabular Code Trace

The following table traces the execution of the function above when n equals 2. Each row in the table shows the values of the function's variables as of a particular step in the execution of the function, where a step corresponds to the evaluation of a line of code terminated by a semicolon. (Note that the values of all variables are the same in steps 6 and 7, because step 7 corresponds to the return statement at the end of the function.)

cycleShiftLeft(2):

Step	n (binary)	oneBitCycleShiftLeft	MAX_MASK (binary)	nShiftedLeft (binary)	bitMask (binary)
0	10	uninitialized	undefined	undefined	undefined
1	10	uninitialized	1 << 30	undefined	undefined
2	10	uninitialized	1 << 30	100	undefined
3	10	uninitialized	1 << 30	100	1
4	10	uninitialized	1 << 30	100	10
5	10	uninitialized	1 << 30	100	100
6	10	1	1 << 30	100	100
7	10	1	1 << 30	100	100

Now you try!

Produce a table like the one above showing the execution of the function when n equals 6. Your table may be hand-written or produced electronically. Either way, the table should trace the function exactly the same way the table above does. Your table should have the same columns and column headings, and it should use exactly the same step-numbering system, English terminology, and bases for representing numbers. If you produce the table on paper by hand, you must submit a clear image of your work as an attachment to an email message.

Hints (added on Wed, 16 Nov 2016)

Hint #1:

Here's an easy and efficient way to approach this assignment: Using a mouse, select the table above. (Be sure to select the entire table. To make sure you've selected the entire table, also select some text before and after the table.) Copy the selected contents. Paste the copied contents into an Excel spreadsheet. For example:

Remove any extraneous text that you pasted. Adjust the widths of the columns. Add rows and modify the contents of cells as needed. Voila!

You have to do the work of reading the code, understanding what it does, and recalling how logical and bitwise operators work, of course. But the mechanics of producing the table can be that easy!

Hint #2:

Still struggling with the concepts?

Explore the fascinating world of one bit cycle shift left >> HERE <<

Grading Rubric

• 15 points will be awarded for emailing your table in the body of an email message, as an attachment to an email message, or as a URL directly referencing your work published on a blog to jspurgeon@vcstudent.org with the string "Exercise[28]" in the subject of the email message on or before the due date.
  • If your work is submitted late, then you will lose 5 points.
  • If your email message does not contain the string "Exercise[28]" in exactly that format or if it contains anything else in the subject line of your email message, then you will lose 5 points.
  • If you send me a URL that does not directly reference a blog post containing your table, or if you send a reference to work stored anywhere other than on a blog, then you will lose 5 points.
• Two points will be awarded for each and every cell in the table that contains the correct value. For example, the table above has 6 columns and 9 rows, yielding 54 cells or 108 points; your table must have the same number of columns and more rows, so it will be worth more points. English words may be in upper, lower or camel case. Numbers must be represented exactly as shown in the example above.
• Up to 15 bonus points will be awarded if a) you post your answer on a blog using HTML table tags, and b) your table looks essentially identical in structure to the one above. (You must use table heading tags for the first row of headings and table data tags for the data rows to receive all of the potential bonus points.)
• The score you receive for this exercise may be weighted to reflect its significance relative to other scores that contributed to your grade for the quarter.

Due Date

For full credit, your work must be received via email (as specified above) by end of day, Friday, November 18, 2016.