How to shift a number?

Question

I want to create a program in MARIE assembly language where I input a number (in HEX mode) and a number of times this number should be shifted to the left or to the right. I thought of storing separate bits in an array, but MARIE does not support accessing single bits of a number. I wonder if it is even possible?

How can I make this happen?

Answer 1

To shift a number to the left is easy: just add the number to itself.

To shift a number to the right you could rotate the input value 15 times to the left. We can detect the leftmost bit of the input value, as that is the sign bit. When the value is negative, we know we should rotate a 1-bit into the result.

Here is how you would do that in C (using int16_t type to mimic the signed word in MARIE) if you would only have addition, subtraction and 0-comparison available as operators:

#include <stdio.h>
#include <stdint.h>

int16_t shiftRight(int16_t num) { // Use 16-bit int
    int16_t result = 1;  // Initialise result with a stop-bit

    do {
        result += result;  // Shift result left
        if (num < 0) {  // Check sign bit of input
            result++;  // Copy that bit into result
        }
        num += num; // Shift input left
    } while (result >= 0);  // Signbit not set? make next iteration
    result += 0x8000;  // Remove signbit, which is the stop-bit
    return result;
}

int main(void) {
    int num;
    
    printf("input (in hexadecimal notation): ");
    scanf("%x", &num);
    int16_t result = shiftRight(num);
    printf("result (in hexadecimal notation): %x\n", result);
    return 0;
}

The main program is just for illustrating that the function shifts the user-given value to the right with one position.

Here is how that translates to MARIE:

Input 
JnS   ShiftRight  / Will shift the value in AC
Output
Halt

/ -------- Subroutine ShiftRight(AC) --------------------------- \
ShiftRight,  Hex 0              / Space for the return address
             Store srNum        / Save the number to be shifted
             Load  srOne        / Initialise result with a stop-bit
             Store srResult
srRepeat,    Add   srResult     / Shift result left
             Store srResult
             Load  srNum        / Check sign bit of input
             SkipCond 000       / Sign bit is 1: skip and add 1 to result
             Jump  srContinue   / Sign bit is 0: don't add 1 to result
             Load  srResult     / Copy that bit into result
             Add   srOne
             Store srResult
             Load  srNum
srContinue,  Add   srNum        / Shift input left
             Store srNum
             Load  srResult     / Check whether done
             SkipCond 000       / Signbit set?
             Jump  srRepeat     / No: make next iteration
             Subt  srSignbit    / Yes: remove signbit, which is the stop-bit
             JumpI ShiftRight   / Return
                          
/ Variables for ShiftRight
srNum,       Dec 0
srResult,    Dec 0
/ Constants for ShiftRight
srOne,       Dec 1
srSignbit,   Hex 8000

If you need to shift a number to the right with 3 positions, then just call the subroutine that many times. But you could also initialise the result with another stop bit (instead of 1 use another power of 2), so that the rotation stops earlier, which represents a shift to the right with multiple positions.

Program for both shifts with shift count

This program reads the number to shift, then how many times it should be shifted, where a positive number indicates a shift to the right, and a negative number indicates a shift to the left. Depending on that sign the call to either ShiftRight or ShiftLeft is made. They return the result in the accumulator which is then output:

             Input  / Get the number that needs shifting
             Store argNum
             Input  / Get the number of times to shift it (positive is right, negative is left)
             SkipCond 000  / Skip if negative
             Jump Positive

Negative,    Store ShiftCount / Negate the shift count in AC
             Clear 
             Subt ShiftCount
             JnS   ShiftLeft
             Jump  Done

Positive,    JnS   ShiftRight
Done,        Output
             Halt

argNum, Dec 0
ShiftCount, Dec 0

/ -------- Subroutine ShiftLeft -------------------------------------------- \
/ In: AC:           the number of times to rotate to the left
/     argNum:       the number to be rotated
/ Out: AC:          the number shifted to the left
/      retOverflow: the bits that were shifted out
/ If number of times < 0, then AC is argNum and overflow is 0.
/ If number of times > 15, then both AC and overflow are 0.
/ -------------------------------------------------------------------------- /
ShiftLeft,   Hex 0              / Space for the return address
             Store slCountDown  / Initialise counter
             Clear              / Initialise overflow and result
             Store retOverflow
             Store slShifted
             Load  slCountDown  / Check range
             Subt  slSixteen    
             SkipCond 000       / Is counter less than 16?
             Jump  slExit       / No: exit with 0
             Load  argNum       / Yes: Initialise shifted result
             Store slShifted
slLoop,      Load  slCountDown
             SkipCond 800       / Counter > 0?
             Jump  slExit       / No: exit loop
             Subt  slOne        / Counting down to 0
             Store slCountDown
             Load  retOverflow 
             Add   retOverflow  / Shift the oveflow left
             Store retOverflow
             Load  slShifted    / Check sign bit of shifted value
             SkipCond 000       / Sign bit is 1: skip and add carry to overflow
             Jump  slContinue   / Sign bit is 0: don't add carry to overflow
             Load  retOverflow  / Copy that bit into the overflow
             Add   slOne
             Store retOverflow
             Load  slShifted
slContinue,  Add   slShifted    / Shift input left
             Store slShifted
             Jump  slLoop
slExit,      Load  slShifted    / Load the result
             JumpI ShiftLeft    /      and return
/ Constants
slOne,       Dec 1
slSixteen,   Dec 16
/ Variables
slCountDown, Dec 0
slShifted,   Dec 0
retOverflow, Dec 0

/ -------- Subroutine ShiftRight -------------------------------------------- \
/ In: AC:       the number of times to shift to the right
/     argNum:   the number to be shifted
/ Out: AC:      the shifted number
/ -------------------------------------------------------------------------- /
ShiftRight,  Hex 0              / Space for the return address
             SkipCond 800       / Skip when count > 0
             Jump  srNoChange   / count <= 0: return AC = argNum
             Store srCount      / Calculate the number of times to shift
             Load  srSixteen    /    in the opposite direction
             Subt  srCount
             SkipCond 800       / Skip when reversed count > 0
             Jump  srExitZero   / original count >= 16 => return 0
             JnS   ShiftLeft    / Perform that opposite shift
             Load  retOverflow  /    and get the overflow
             JumpI ShiftRight
srNoChange,  Load  argNum
             JumpI ShiftRight
srExitZero,  Clear 
             JumpI ShiftRight
             
/ Constant
srSixteen,   Dec 16
/ Variable
srCount,     Dec 0