Downloading...
nomul
not smarter than your compiler
v.0.21 | 03/30/2018
Express the multiplication of an integer i with a given constant multiplier using only bitshifts, integer addition and substraction.
Reading the result
The first line is aligned to column 0 and gives the straightforward solution of adding-up all bits.
Further below, another line in the first column (starting with '|'), gives an alternative solution based on a first place substraction.
If further solutions are found they will be indented and prefixed with a '|' character.
For these additional solutions, indented parts have to be read in conjunction with the previous line[1], up to the '|' in the indented line.
[1]: and possibly (partly) the next higher line in a recursive fashion[1]
Example
Multiplier: 1000000
+(i <<19) +(i <<18) +(i <<17) +(i <<16) +(i <<14) +(i << 9) +(i << 6)
|+(i << 7) -(i << 6)
|+(i <<10) -(i << 8) -(i << 7) -(i << 6)
|+(i <<15) -(i <<13) -(i <<12) -(i <<11) -(i <<10) -(i << 8) -(i << 7) -(i << 6)
|-(i << 9) +(i << 6)
|+(i <<20) -(i <<15) -(i <<13) -(i <<12) -(i <<11) -(i <<10) -(i << 8) -(i << 7) -(i << 6)
|-(i << 9) +(i << 6)
|-(i <<14) +(i << 9) +(i << 6)
|+(i << 7) -(i << 6)
9 solutions found in 12 milliseconds
In the above example, nine solutions are presented to multiply i with 1000000 of which the shortest has 5 elements:
+(i <<20) -(i <<15) -(i <<14) +(i << 9) +(i << 6)
Thoughts
You'll have to consider possible overflows manually based on your input range!
For very long operations, you should copy the output into a text editor and disable line wrapping to read it cleanly.
All of the tool's calculations are on an int64_t [-9223372036854775808 .. +9223372036854775807]. Values out of the range will be clamped.
Source code
nomul.c