Implementing a logical shift right

Question

So I'm working on the nand2tetris project, and I want to implement shift right logical on a software level since the hardware doesn't support it.

I know shift right logical is a division by two. So my first shot at implementing it would count the number of times I was able to subtract 2 from the initial value before the value became 0 or negative. Similar for if the number was negative.

But, I've found a scenario where it's not working. I want to shift right -27139. Well the binary value after shifting is 19199. It should be 19198. Thus I'm looking for a new way to implement the shift.

I can and values, or values, add and subtract, and that's about all I have at my disposal.

OSFTW

Here's the code I have in the Hack implementation's assembly language:

//============================================================
// SLR: Shift Logical Right (by 1)
//============================================================

(SLR)

@SLR.1              // Load value
D=M
@SLR.2
M=0                 // Clear variables
@SLR_POSITIVE_LOOP      // If value is positive, go to the positive loop
D;JGT


(SLR_NEGATIVE_LOOP)
@SLR.1              // Add 2 to value, since it's negative
M=M+1
M=M+1
@SLR.1              // If initial value was negative and current value is positive or zero, jump out of loop
D=M
@SLR_NEG
D; JGE
@SLR.2              // If value is negative, add 1 to SLR.2 (we're dividing)
M=M+1
@SLR.1              // If value is less than 0, restart the loop
D=M
@SLR_NEGATIVE_LOOP
D; JLT

(SLR_NEG)
@SLR.2
D=M
D=!D                // Invert the result
D=D+1               // Add 1 to finish converting
@32767              // And it with 0111111111111111 to clear the sign bit
D=D&A
@SLR.2
M=D                 // Set value
@SLR_END                        // Jump to end of loop
0;JMP

(SLR_POSITIVE_LOOP)
@SLR.1              // Subtract 2 from value
M=M-1
M=M-1
@SLR.1              // If initial value was positive and current value is negative or zero, jump out of loop
D=M
@SLR_END
D; JLE
@SLR.2              // If value is still positive, add 1 to SLR.2 (we're dividing)
M=M+1
@SLR.1              // If value is greater than 0, restart the loop
D=M
@SLR_POSITIVE_LOOP
D; JGT


(SLR_END)               // Loop is over. Set value of SLR.1 to that of SLR.2, for return purposes

@SLR.2                                  // Place result in correct place
D=M
@SLR.1
M=D

@SLR.0             // Return to calling function
A = M
0; JMP

Greenhead

If you subtract an odd number by 2 then it'll always be odd, so the result. Also, repeatedly subtract is not a good solution since it'll cause the program to loop thousands of times – Berkeleianism

Repeatedly subtracting a signed number by 2 is like arithmetic shift, because the sign bit is always copy to the result (-27139 - 2 = -27137), which rounds toward -Inf. That's why you see the result. To shift zero in, do a unsigned subtraction ((unsigned)-27139 - 2 =38397 - 2 = 38395) – Berkeleianism

shift right then repair the msbit to match the next to msbit. much less work much faster. if this is an unsigned number then you dont have to do that at all, just shift right and that is a divide by 2. – Eliezer

a similar question here – Berkeleianism

It's ony division by two if it's positive. – Soembawa

Answer 1

A logical shift of a number either left or right equals copying N-n bits from one word of N bits to another. Thus:

unsigned int a = 0x1321;
unsigned int b = 0;
unsigned int mask1 = 1;
unsigned int mask2 = 1 << n;  // use repeated addition for left shift...
int i;
for (i = 0; i < N-n; i++) {
    if (a & mask2)
        b|= mask1;
    mask1 += mask1;
    mask2 += mask2;
}

Swapping mask1 and mask2 would implement left shift (with bitwise operations only).

Waldgrave

I'm assuming here that N is the number of bits in the value? Also this may sound dumb, but how do I treat a number that's interpreted as a signed integer, as an unsigned integer? Just operate on it as if it were unsigned? – Greenhead

N is typically 32, i.e. the number of bits in the machine word. Logical operators (or even add/sub in 2's complement) do not make any difference inbetween signed and unsigned integers. So yes: just do it! – Waldgrave

Answer 2

In keeping with the nature of the Nand2Tetris course, I've tried to walk a line in this answer, giving examples of Hack assembly coding techniques and general algorithms, but leaving the final code as an exercise.

The Hack ALU does not have any data paths that connect bit N with bit N-1. This means that right-shifts and rotates must be implemented using left rotates. (Note: left = most significant bits, right = least significant bits)

A left-shift is easy, since it's just multiplication by 2, which is itself just self-addition. For example:

// left-shift variable someVar 1 bit

@someVar     // A = address of someVar
D = M        // D = Memory[A]
M = M + D    // Memory[A] = Memory[A] * 2

Left-rotate is a bit more difficult. You need to keep a copy of the leftmost bit, and move it into the rightmost bit after doing the multiply. Note however that you have a copy of the original value of "someVar" in the D register, and you can test and jump based on its value -- if the leftmost bit of D is 1, then D will be less than zero. Furthermore, note that after you multiply "someVar" by 2, it's rightmost bit will always be 0, which makes it easy to set without changing any of the other bits.

Once you have left-rotate, right-rotate is straightforward; if you want to left-rotate N bits, you instead right-rotate 16-N bits. Note that this assumes N in range 0-15.

Right-shift is the most complicated operation. In this instance, you need to first do the right-rotate, then generate a mask that has the upper N bits set to zero. You AND the result of the right-rotate with the mask.

The basic way to generate the mask is to start with -1 (all bits set) and add it to itself N times; this makes the rightmost N bits of the mask 0. Then left-rotate this 16-N times to move all the 0 bits to the leftmost N bits.

However, this is a lot of cycles, and when programming in assembly language, saving cycles is what it's all about. There are a couple of techniques you can use.

The first is using address arithmetic to implement the equivalent of a case statement. For each of the 16 possible rotate values, you need to load a 16 bit mask value into the D register, then jump to the end of the case. You have to be careful because you can only load 15 bit constants using the @instruction, but you can do the load and unconditional jump in 6 instructions (4 to load the full 16 bit constant, and 2 to jump).

So if you have 16 of these starting at location (CASE), you just need to multiply N by 6, add it to @CASE, and jump to that location. When thinking about how to multiply by 6, keep in mind one of the really cute features of the HACK instruction set; you can store the results of an ALU operation in multiple registers simultaneously.

The most efficient solution, however, is to precompute a mask table. During your program initialization, you generate the 16 bit masks and store them in some fixed location in memory, then you can just add N to the address of the start of the table and read the mask.

Since the HACK CPU can't access the program ROM other than to fetch instructions, you can't store the table in ROM, you have to use several instructions per table entry to load the value into the D register and then save it into RAM. I ended up written a simple python script that generates the code to initialize tables.

Shelled

Answer 3

It gets easier if you treat the value to shift as unsigned, since a logical right shift won't preserve the sign anyway. Then you just subtract 2 repeatedly until the result is less than 2, at which point the number of subtractions is your quotient (i.e. the right-shifted value).

An example implementation in C:

int lsr(int valueToShift)
{
    int shifted = 0;
    uint16_t u = valueToShift;

    while (u >= 2) {
        u -= 2;
        shifted++;
    }

    return shifted;
}

Dynatron

Answer 4

You should use binary or hexadecimal since using decimal makes it hard to imagine the number representation.

If you have arithmetic shift but not logical shift, the most obvious solution would be clearing the top bits if it's negative

int LogicalRightShift(int x, int shift)
{
    return (x >> shift) & ((1U << (CHAR_BIT*sizeof(x) - shift)) - 1);
    // or
    return (x >> shift) & (~((~0) << (CHAR_BIT*sizeof(x) - shift)));
}

If you don't have arithmetic right shift either you can copy it bit-by-bit

int LogicalRightShift(int x, int shift)
{
    // assuming int size is 32
    int bits[] = {  0x1,        0x2,        0x4,        0x8,        0x10,       0x20,       0x40,       0x80,
                    0x100,      0x200,      0x400,      0x800,      0x1000,     0x2000,     0x4000,     0x8000,
                    0x10000,    0x20000,    0x40000,    0x80000,    0x100000,   0x200000,   0x400000,   0x800000,
                    0x1000000,  0x2000000,  0x4000000,  0x8000000,  0x10000000, 0x20000000, 0x40000000, 0x80000000
    }
    int res = 0;
    for (int i = 31; i >= shift; i++)
    {
        if (x & bits[i])
            res |= bits[i - shift];
    }
    return res;
}

Another way is repeatedly dividing by 2. Or you can store the powers of 2 in a lookup table and divide by that power. This way it may be slower than the bit copying method above if you don't have hardware divider but still much faster than having to subtract thousands of times like your method. To shift -27139 (38397) right 1 bit you need to subtract 2 from the number 9599 times, and even more if the number is larger or if you need to shift a different number of bits

Berkeleianism

As I understood the question, there was no support for shift operations (<< and >>), which is why the OP wanted to implement it using the instructions that he had available. – Dynatron

@Dynatron as I understood there was no support for logical shift operations, so I use arithmetic shift instead – Berkeleianism

I unfortunately don't have a shift right arithmetic. I have to implement that as well. – Greenhead

Answer 5

A faster way might be to use addition. For a crude example:

uin32_t LSR(uint32_t value, int count) {
    uint32_t result = 0;
    uint32_t temp;

    while(count < 32) {
        temp = value + value;
        if(temp < value) {                // Did the addition overflow?
            result = result + result + 1;
        } else {
            result = result + result;
        }
        value = temp;
        count++;
    }
    return result;
}

The basic idea is to shift a 64-bit unsigned integer left "32 - count" times then return the highest 32 bits.

In assembly, most of the code above (the branches, etc) would hopefully become something like add value, value then add_with_carry result, result.

Meanie