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.

Solution 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.

Solution 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.

Comments

[Will Haynes]

This could work, but it seems to me that there must be a simpler to implement it (like adding it to itself in the left shift) You are correct that this is homework, and it's due this Wednesday (apr 11), so I have a couple of days to look for a better solution before I "brute force" it with this approach.

[Russell Zahniser]

This isn't exactly "brute force"; it's just 9 lines of code including setup.

[committedandroider]

Can you take a look at this? stackoverflow.com/questions/30017878/where-is-32768-coming-f‌​rom

[Tommylee2k]

a way around the reminder 1 would be, to and the register with 0xFE before dividing. but this solution looks like a very slow one for me

[Peter Cordes]

You can add instead of or if you know there is no carry. This is the case here because you work one bit at a time.