6

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.

Will Haynes
  • 758
  • 3
  • 8
  • 15

4 Answers4

7

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.

Russell Zahniser
  • 16,188
  • 39
  • 30
  • 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. – Will Haynes Apr 10 '12 at 00:26
  • This isn't exactly "brute force"; it's just 9 lines of code including setup. – Russell Zahniser Apr 10 '12 at 13:29
  • Excellent solution. @RussellZahniser is this the simplest solution for a logical shift right? or there exists a simpler approach? – Aishgadol Feb 03 '23 at 18:56
1

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.

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680
1

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.

user3054804
  • 11
  • 2
  • 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. – Peter Cordes Nov 01 '17 at 02:02
0

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.

meüto
  • 1
  • 1
    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 – Tommylee2k Mar 10 '16 at 07:18