Sun, 20 Oct 2013, 12:18



A student writes:

 
> Dr.Patt,
> I understand that to shift a number of binary digits to the right 
> it is necessary to divide by 2. But I am really having trouble with 
> how to actually do that in a program. Can you please explain how 
> I can shift to the right with the instructions that are available 
> by the LC-3?
> Thank you,
> <<name withheld to protect the student who wants to right shift>>


Let's look at what it takes to do a right shift.

Suppose instead of simply shifting (left or right), I in addition 
replaced the empty slot the shift created with the bit I shifted out.  
We actually have a name for that.  It is called ROTATE, and many 
computers have a ROTATE instruction.

Example: Suppose we have bit vector: 1111110000000000.  If I did a
ROTATE to the left one bit, I would end up with 1111100000000001.  
If instead, I did a ROTATE to the right, I would end up with 
0111111000000000.  

Second point.  A ROTATE of k bits to the right is the same as a ROTATE of
how many bits to the left?

Finally, I do not need to tell you how to left shift k bits, correct?
To right shift by k bits, you need to (a) left shift by some number of bits,
(b) find a way to each time put the bit shifted out of bit[15] back into 
bit[0], and (c) get rid of some of the original bits (those that are to 
shifted out due to the right shift you are trying to accomplish.

Can you put these three things together to do a right shift?

Hope this helps.

Good luck getting the program done today.

Yale Patt



Yale Patt



What would the contents of your register be if you right-shifted k bits.
Pick some value of k.

How many of the original bits are no longer present?  Which ones?  How
do you change your original bit vector to have 0s in those bit positions.

Now then, I assume you know how to left shift.  You know that if you left shift