Question

Logical shift right without dedicated shift instruction

I am working with an assembly language that does not contain either multiply, divide, or bit-shift instructions. I am aware that a left bit-shift can be achieved by just adding the same number to itself - add A, A - but I am unsure about a right bit-shift. How would I go about implementing a right bit-shift with instructions such as add, sub, not, and and or?

There is also adc and sbb if that helps. It's an instruction set for a homebrew computer I was designing, and I wanted to see if it was possible with the instruction set I have implemented.

The full instruction set is add, sub, adc, sbb, nand, or, cmp, mv, ld, st, lda, lpm, push, pop, jnz, and halt.

 5  122  5
1 Jan 1970

Solution

 7

There are several ways to accomplish a right shift on a limited machine — though I think most of them require compare & branch operations, since they involve both looping and conditional operation.


Right shift is like dividing by 2.  So, one way is by division by 2, which your machine doesn't have directly, but can be simulated with repetitive subtraction.  Write a loop to subtract 2 (add -2) and count how many times you can do that; that count will be the original value divided by 2 (leaving the remainder as leftover).


Otherwise, we can copy bits, one at a time, to a new location.

  • Start with a zero value as the result value, and a copy of the original value if you need it after, otherwise the following will modify the original.

  • Initialize a loop counter.

  • Loop:

    • Test whether the high bit is set in the original if so then add 1 to the result value.  To test the high bit, check if it is negative.

    • Increment/decrement and test loop counter, if at 15 iterations then exit the loop.  (Assuming 16 bit machine/word size here).

    • Otherwise, double the original, and double the result value, and repeat.

That will accomplish a logical right shift.  Copy the original sign bit if you want arithmetic right shift.

That copies a bit at a time from the left (most significant), and if you went 16 iterations, you'd have an exact copy of the original, but by stopping short at 15 iterations, you have a 1-bit right shift of the original, and, the original is reduced to the remainder (though now in the msb position).


Alternatively, start with two values having exactly one bit set, each:

  • The first, call it input position is 0000000000000010₂, and

  • The second, call it output position is 0000000000000001₂

  • And a result value initialized to 0.

  • Then loop 15 times doing the following:

    • "and" the original value with the input position
    • if that value is non-zero then "or" the output position into the result value
    • double the input position (left shift)
    • double the output position (left shift)

Yet another approach (very inefficient), based on trying possibilities:

  • start a loop counter, say i, at 0
  • loop
    • if i + i equals the original value, then stop, answer is i
    • if i + i + 1 equals the original value, same
    • add 1 to i
    • repeat
2024-07-04
Erik Eidt