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