LC3 Assembly Bitwise Right Shift

Question

What I need to do it implement both a bitwise left shift, and a bitwise right shift using LC-3 Assembly. Basically, every bit has to be moved over one space in the direction of the shift, and a zero fills the empty space created.

Examples:

Right Shift:

 01001001
 00100100→

Left Shift:

 01001001
←10010010

I've successfully implemented a left shift, by taking the binary string, and adding it to itself.

I'm stumped on how to perform a right shift. Any thoughts would be greatly appreciated. I have AND, NOT, ADD operations, data movement operations, seven registers to store values and whole range of memory. I just need some basic ideas how it could be implemented.

If you need a LC-3 Instruction Set reference, there is one here.

Answer 1

Suppose you set up R2 so that it has just a single bit set. Then, if you do an AND with another register and branch on the Z condition, you are testing whether that bit is set. If it is, you want to set the previous bit in your "result" register.

If you then shift your single-bit register over one place and repeat in a loop, you should have what you need.

(Apologies if this is vague; since this is presumably homework I'm trying to avoid just giving you the answer)

Edit:

So, suppose your input is 01001011. You start with an output of 00000000, an input mask of 00000010, and an output mask of 00000001. You do the AND and find that it is nonzero, so you add your output mask to the output. Then you shift both masks over to get 00000100 and 00000010.

On the next time through the loop, the AND is zero, so you add nothing, and so forth. The loop terminates when shifting the mask makes it zero.

Answer 2

Wow, that's quite a minimal instruction set.

If you have 256 bytes of memory available, then a lookup table might be the way to go.

You could do it without data memory using a loop over each bit position, using AND to extract the bit.