LC3 Assembly Bitwise Right Shift

问题:

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.

回答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.

回答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.

回答3:

You need two masks. Both of them are a single "1" with the rest of them "0"s. Both are initialized to 0000 0000 0000 0001, but one of them is left-shifted by an amount that you want the original number to be right-shifted. We'll call that Mask1. The un-shifted number will be Mask2.

Compare Mask1 with the original number. If (Mask1 "and" input) > or < 0, "or" Mask2 with output and then left-shift both Masks.

In either case, left-shift both Masks and try again until there are no more bits in the input to test.

LC-3 does not have a bitwise "or." You will have to "not" both operands, "and" them, then "not" the result for a bitwise "or."

The reason you are testing whether or not Mask1 "and" input is > or < 0 is because if it is zero, we want to do nothing. If the result of "and"ing these operands is > 0, then that means that the position tested found a "1" and it needs to be printed to the result. If the mask has been left-shifted to become 1000 0000 0000 0000, that is technically a negative number. The "and" of that and any number with a "1" in that position will also be a negative number.

回答4:

Assuming a leading 0 you can just divide by 2, by subtracting again and again.

So count how often you can ADD RX, RX, #-2

I'm sure there is also a way to work around a leading 1.