For nonnegative (or unsigned) integers only. Otherwise, add more
complexity. (Well, not add, that's not bitwise. Shift in?)
[1] Initialize product to zero.
[2] While multiplicand is greater than zero, add (see below)
multiplier to product and decrement multiplicand.
Decrement is not bitwise. Change that to add ~0U.
Or to the specialized algorithm: loop changing all trailing zero bits
to one and (then) the last one to zero.
Or, even better, use "Russian peasant":
[2] While multiplicand is greater than zero,
[2A] if low bit of multiplicand is set, add multiplier to product.
[2B] (always) shift multiplier left and multiplicand right.
To add:
[1] Initialize sum to augend
[2] Exclusive OR sum and addend
[3] AND addend and sum, shift this result left one position
[4] Result from [2] replaces sum
[5] Result from [3] replaces addend
[6] If addend isn't zero, continue from [2]
You could do full-adder logic with carry-save, and only complete the
ripples at the end. But I don't think it's feasible to do look-ahead.
Or at least not worth the trouble.
drHTHtOP
- David.Thompson1 at worldnet.att.net