I was quite obsessed with the idea of optimizing integer multiplication by using bit shifts so that I noticed a beautiful pattern in the binary representation when I looked at some results of previous equations, I wrote. I wrote a small brute-force algorithm to get all possible numbers which can be optimized a bit as constant factor of a multiplication. The algorithm is implemented in JavaScript, so if you're interested in the source code, feel free to read it.
0 * n 000000000000 n - n 1 * n 000000000001 n 2 * n 000000000010 (n << 1) 3 * n 000000000011 (n << 1) + n 4 * n 000000000100 (n << 2) 5 * n 000000000101 (n << 2) + n 6 * n 000000000110 (n << 2) + (n << 1) 7 * n 000000000111 (n << 3) - n 8 * n 000000001000 (n << 3) 9 * n 000000001001 (n << 3) + n 10 * n 000000001010 (n << 3) + (n << 1) 12 * n 000000001100 (n << 3) + (n << 2) 14 * n 000000001110 (n << 4) - (n << 1) 15 * n 000000001111 (n << 4) - n 16 * n 000000010000 (n << 4) 17 * n 000000010001 (n << 4) + n 18 * n 000000010010 (n << 4) + (n << 1) 20 * n 000000010100 (n << 4) + (n << 2) 24 * n 000000011000 (n << 4) + (n << 3) 28 * n 000000011100 (n << 5) - (n << 2) 30 * n 000000011110 (n << 5) - (n << 1) 31 * n 000000011111 (n << 5) - n 32 * n 000000100000 (n << 5) 33 * n 000000100001 (n << 5) + n 34 * n 000000100010 (n << 5) + (n << 1) 36 * n 000000100100 (n << 5) + (n << 2) 40 * n 000000101000 (n << 5) + (n << 3) 48 * n 000000110000 (n << 5) + (n << 4) 56 * n 000000111000 (n << 6) - (n << 3) 60 * n 000000111100 (n << 6) - (n << 2) 62 * n 000000111110 (n << 6) - (n << 1) 63 * n 000000111111 (n << 6) - n 64 * n 000001000000 (n << 6) 65 * n 000001000001 (n << 6) + n 66 * n 000001000010 (n << 6) + (n << 1) 68 * n 000001000100 (n << 6) + (n << 2) 72 * n 000001001000 (n << 6) + (n << 3) 80 * n 000001010000 (n << 6) + (n << 4) 96 * n 000001100000 (n << 6) + (n << 5) 112 * n 000001110000 (n << 7) - (n << 4) 120 * n 000001111000 (n << 7) - (n << 3) 124 * n 000001111100 (n << 7) - (n << 2) 126 * n 000001111110 (n << 7) - (n << 1) 127 * n 000001111111 (n << 7) - n 128 * n 000010000000 (n << 7) 129 * n 000010000001 (n << 7) + n 130 * n 000010000010 (n << 7) + (n << 1) 132 * n 000010000100 (n << 7) + (n << 2) 136 * n 000010001000 (n << 7) + (n << 3) 144 * n 000010010000 (n << 7) + (n << 4) 160 * n 000010100000 (n << 7) + (n << 5) 192 * n 000011000000 (n << 7) + (n << 6) 224 * n 000011100000 (n << 8) - (n << 5) 240 * n 000011110000 (n << 8) - (n << 4) 248 * n 000011111000 (n << 8) - (n << 3) 252 * n 000011111100 (n << 8) - (n << 2) 254 * n 000011111110 (n << 8) - (n << 1) 255 * n 000011111111 (n << 8) - n 256 * n 000100000000 (n << 8) 257 * n 000100000001 (n << 8) + n 258 * n 000100000010 (n << 8) + (n << 1) 260 * n 000100000100 (n << 8) + (n << 2) 264 * n 000100001000 (n << 8) + (n << 3) 272 * n 000100010000 (n << 8) + (n << 4) 288 * n 000100100000 (n << 8) + (n << 5) 320 * n 000101000000 (n << 8) + (n << 6) 384 * n 000110000000 (n << 8) + (n << 7) 448 * n 000111000000 (n << 9) - (n << 6) 480 * n 000111100000 (n << 9) - (n << 5) 496 * n 000111110000 (n << 9) - (n << 4) 504 * n 000111111000 (n << 9) - (n << 3) 508 * n 000111111100 (n << 9) - (n << 2) 510 * n 000111111110 (n << 9) - (n << 1) 511 * n 000111111111 (n << 9) - n 512 * n 001000000000 (n << 9) 513 * n 001000000001 (n << 9) + n 514 * n 001000000010 (n << 9) + (n << 1) 516 * n 001000000100 (n << 9) + (n << 2) 520 * n 001000001000 (n << 9) + (n << 3) 528 * n 001000010000 (n << 9) + (n << 4) 544 * n 001000100000 (n << 9) + (n << 5) 576 * n 001001000000 (n << 9) + (n << 6) 640 * n 001010000000 (n << 9) + (n << 7) 768 * n 001100000000 (n << 9) + (n << 8) 896 * n 001110000000 (n << 10) - (n << 7) 960 * n 001111000000 (n << 10) - (n << 6) 992 * n 001111100000 (n << 10) - (n << 5) 1008 * n 001111110000 (n << 10) - (n << 4) 1016 * n 001111111000 (n << 10) - (n << 3) 1020 * n 001111111100 (n << 10) - (n << 2) 1022 * n 001111111110 (n << 10) - (n << 1) 1023 * n 001111111111 (n << 10) - n 1024 * n 010000000000 (n << 10) 1025 * n 010000000001 (n << 10) + n 1026 * n 010000000010 (n << 10) + (n << 1) 1028 * n 010000000100 (n << 10) + (n << 2) 1032 * n 010000001000 (n << 10) + (n << 3) 1040 * n 010000010000 (n << 10) + (n << 4) 1056 * n 010000100000 (n << 10) + (n << 5) 1088 * n 010001000000 (n << 10) + (n << 6) 1152 * n 010010000000 (n << 10) + (n << 7) 1280 * n 010100000000 (n << 10) + (n << 8) 1536 * n 011000000000 (n << 10) + (n << 9) 1792 * n 011100000000 (n << 11) - (n << 8) 1920 * n 011110000000 (n << 11) - (n << 7) 1984 * n 011111000000 (n << 11) - (n << 6) 2016 * n 011111100000 (n << 11) - (n << 5) 2032 * n 011111110000 (n << 11) - (n << 4) 2040 * n 011111111000 (n << 11) - (n << 3) 2044 * n 011111111100 (n << 11) - (n << 2) 2046 * n 011111111110 (n << 11) - (n << 1) 2047 * n 011111111111 (n << 11) - n 2048 * n 100000000000 (n << 11) 2049 * n 100000000001 (n << 11) + n 2050 * n 100000000010 (n << 11) + (n << 1) 2052 * n 100000000100 (n << 11) + (n << 2) 2056 * n 100000001000 (n << 11) + (n << 3) 2064 * n 100000010000 (n << 11) + (n << 4) 2080 * n 100000100000 (n << 11) + (n << 5) 2112 * n 100001000000 (n << 11) + (n << 6) 2176 * n 100010000000 (n << 11) + (n << 7) 2304 * n 100100000000 (n << 11) + (n << 8) 2560 * n 101000000000 (n << 11) + (n << 9) 3072 * n 110000000000 (n << 11) + (n << 10) 4096 * n 1000000000000 (n << 11) + (n << 11)
As you can see, on the left most column, a simple multiplication formula is given, which can also be expresed by the right most column. The basic approach was already discussed in the prior article, where I developed the following relation:
\[(2^x - 2^y)\cdot n = (n<<x)-(n<<y)\]
I want to give you an example which is not so trivial on the first sight. Please consider the equation 496 * n . The table above says, we can describe 496 by \(2^9 - 2^4\), so that we could rewrite the formula to \((n << 9) - (n << 4)\)
and after the reshaping, we'll get the same result as with a perhaps slower multiplication. Of course, the trick will only bring a performance benefit, if the architecture uses a slow multiplication implementation and fast binary/subtraction operations and if the compiler does not already do a similar thing.