Need help for a LC-3 programming problem!

Build a subroutine that takes, as a parameter, the value of a register and right-shifts it by one bit,

losing the trailing bit, and filling in the empty leading bit with 0:

You have to read & understand this exercise, but you don't need to code it - you just need to show the algorithm you would use (use the outline below).

Example:

(R1) xABCD ; (b1010 1011 1100 1101)

[call the right-shift subroutine]

[now (R1) == x55E6 == b0101 0101 1110 0110]

Note how we shifted-in a 0 when we did the right-shift, and "lost" the 1 in the lsb?

This is called a logical right shift; there are two other variations, the arithmetic right-shift (which

maintains the sign bit rather than always shifting-in a 0 to the msb); and a right-rotate, which shifts in

into the msb the bit shifted out of the lsb. For the moment, we will just deal with the logical right-shift.

Discussion:

Alright, lets think about this thing. When we left-shift, we are doubling the number (aka:

multiplying it by two - aka: adding it to itself - aka: ADD R1, R1, R1), right? So if left-shift is

multiplication, then what might right-shift be?

Yep, you guessed it: Division. If you left-shift the number 2, you get 4. If you right-shift 4, you go

back to having 2. So, division. Right. Got it.

How in blazes are we supposed to right shift?! the TA said rhetorically.

[Whacky Student]: If left-shifting is ADDing a number to itself, then right-shift must be

subtracting it from itself, right?

[TA]: *blank stare*

[Less Whacky Student]: *whispers* Dude, that would make it zero.

[Whacky Student]: *facepalm*

Well, sadly, there is no super-simple way to perform a binary right-shift. Still, it's not insanely

difficult. Lets think about it:

Left-shifting is short and sweet: add the number to itself.

Right-shifting is not quite as simple. There is no way to directly do it in software.

Hmm how else can we mess around with the bits? We can shove them left and shift-in

a 0 every time to the lsb (thats a logical left-shift) but what if instead we rotated the

bits (i.e. take the msb being shifted out, and shift it in as the new lsb)?Hmmm:

Given the 4-bit (unsigned) number xC == b1100 == #12 (UNsigned magnitude)

[Rotate left, noting that msb is 1, which gets rotated in to the lsb]

Now we have b1001 == #9

[Rotate left, noting that msb is again 1, which gets rotated in to the lsb]

Now we have b0011 == #3

[Rotate left, noting that msb is now 0, which gets rotated in to the lsb]

Now we have b0110 == #6 - note that msb is now 0

Ok, this is boring. Lets stop.

Hey wait! Oh my gosh!

We have 12/2 == 6 now! Howd that happen?!?

[This is where you, the Less Whacky Student, fill in the blanks ]

Note: This only works for unsigned representation. How could it be made to work for two's

complement representation?