right shift with the Hack ALU

[ybakos]

One of my students was exploring a different approach to Mult.asm:

"I wanted to try out the conventional/faster method of multiplying 2 numbers using shifting. I know left shifts are achieved by adding a number to itself (*2), but I can't figure out how to right shift given AND OR NOT + - ."
"I was planning on using the right shift to get the LSB of one operand and the left shift to move the other operand over to add it as the next multiple of 2. I know how to hard-code 16m lines - but if I have shifts, I can do this with just 16 loops of n."

I haven't been able to figure out an elegant way to conduct a right shift using the Hack ALU. Do any of you have any ideas?

[cadet1620]

ybakos wrote

I haven't been able to figure out an elegant way to conduct a right shift using the Hack ALU. Do any of you have any ideas?

I've written multiplication routines for way too many microprocessors that didn't have it in hardware that I instinctively started to write it this way when I got here in the book, and tripped over the lack of right shift.

I thought about this for a bit, and decided that there can be no easy way to right shift because there is no data path from bit n to bit n-1 in the ALU. Addition carry provides the data path from bit n to bit n+1.

Left rotate can be implemented as:

int ROL (int n) {
    if (n<0)
        return n+n+1;
    else
        return n+n;
    }

and then right shift(n) is implemented as 16-n left rotates followed by some housekeeping depending on whether it needs to be arithmetic or logical.

Yuck.

What I did was turn the multiplication upside down. Since it's easy to test the sign bit, add up the partial products from bottom to top in the long multiplication layout, shifting the multiplier and product to the left for each iteration.

[Another interesting challenge--implementing double precision integers without a carry flag.]

--Mark

[ybakos]

cadet1620 wrote

... there is no data path from bit n to bit n-1 in the ALU ...

That's the key point, I think. Thanks for sharing!