I got a little obsessed with the idea of speeding up a multiplication by a constant using nothing but bit shifts and additions. While trying out a few constants by hand, a pattern in their binary representations kept jumping out at me, so I wrote a small brute-force script to map out systematically which constants can be built cheaply this way. What follows is the result, together with the math that explains why it works.
From Bits to Shifts and Adds
Multiplying a variable \(n\) by a fixed constant \(c\) is, in the end, just repeated addition, and on a binary machine that repeated addition has a very concrete shape. Write \(c\) in binary as a sum of powers of two,
\[c=\sum_i b_i\cdot 2^i,\qquad b_i\in\{0,1\},\]
and multiply both sides by \(n\):
\[c\cdot n=\sum_i b_i\cdot\left(n\cdot 2^i\right).\]
Since multiplying by \(2^i\) is exactly what a left shift does, \(n\cdot 2^i = n\ll i\), this is nothing more than binary long multiplication: every set bit of \(c\) contributes one shifted copy of \(n\), and all the shifted copies are added up. As code, that is a direct transcription of the sum above:
long multiply(long n, unsigned c) {
long result = 0;
for (int i = 0; c != 0; i++, c >>= 1) {
if (c & 1) {
result += n << i;
}
}
return result;
} For a constant with many set bits this naive scheme is not obviously cheaper than an actual hardware multiplier, but it only ever uses shifts and additions, which is the whole point on architectures where a multiply instruction is slow, absent, or simply the pricier operation.
Collapsing Runs of Ones
Plenty of constants have long runs of consecutive one bits, for example \(496=0\text{b}111110000\). The naive scheme above would spend one addition per set bit, but a run of ones can always be replaced by a single subtraction. A run occupying bits \(y\) through \(x-1\) sums to a familiar geometric series,
\[\sum_{k=y}^{x-1}2^k=2^x-2^y,\]
so multiplying by exactly that block reduces to
\[(2^x-2^y)\cdot n=(n\ll x)-(n\ll y).\]
For \(496=2^9-2^4\), this turns five additions (one per set bit) into a single subtraction of two shifted values:
return (n << 9) - (n << 4); The same idea also explains simple cases like \(15=2^4-1\), giving \((n\ll 4)-n\) instead of adding four shifted copies of \(n\).
Searching for the Cheapest Combination
Not every constant is a single run of ones, though; many are one or two separate runs, or a run plus a lone bit, and it is not always obvious by eye which combination of shifts is cheapest. Rather than reasoning about every constant by hand, I let a small brute-force search do it: start from every single power of two \(2^i\) (cost one shift), then combine every pair \(2^i\) and \(2^j\) with a \(+\) or \(-\) and keep any resulting value that was not already reachable more cheaply. Sorted by size, this produces a table of the cheapest two-term shift expression for every constant that admits one, up to \(2^{12}\):
Beyond Two Terms: The Non-Adjacent Form
The pairwise search above only ever looks two shifted terms deep, so it misses constants that genuinely need three or more signed terms to reach their cheapest form. Take \(23=0\text{b}10111\): its four set bits do not reduce to a single run, and no combination of two signed powers of two reproduces it exactly, so the two-term search leaves it out of the table entirely.
There is a general recipe that handles this and every other constant optimally, known as the Non-Adjacent Form (NAF). It builds a signed binary representation, with digits in \(\{-1,0,1\}\) instead of just \(\{0,1\}\), one digit at a time from the least significant end:
\[ d_i=\begin{cases} 0 & c\text{ even}\\ 2-(c\bmod 4) & c\text{ odd} \end{cases}, \qquad c\leftarrow \frac{c-d_i}{2}. \]
Whenever \(c\) is odd, this rule chooses \(d_i=1\) if \(c\equiv 1\pmod4\) and \(d_i=-1\) if \(c\equiv 3\pmod4\); either way, \(c-d_i\) is a multiple of \(4\), so the very next digit is forced to \(0\). That is exactly what "non-adjacent" refers to: no two nonzero digits ever sit next to each other. This greedy rule is not just convenient, it provably yields the signed binary representation with the fewest nonzero digits among all possible ones for that integer.
Running it on \(23\): \(23\equiv3\pmod4\) gives \(d_0=-1\), leaving \(c=6\); halving twice with no odd remainder gives \(d_1=d_2=0\), leaving \(c=3\); \(3\equiv3\pmod4\) gives \(d_3=-1\), leaving \(c=2\); one more halving gives \(d_4=0\), leaving \(c=1\); and \(1\equiv1\pmod4\) gives \(d_5=1\). Reading off the nonzero digits reconstructs
\[23=2^5-2^3-2^0,\]
three signed terms (two subtractions) instead of the four terms (three additions) the naive bit-by-bit scheme would need.
Does This Still Pay Off?
All of this only applies when the constant is fixed at compile time or hardware-design time; it says nothing about multiplying two genuinely variable numbers. And even for constants, this exact rewrite is one of the standard tricks an optimizing compiler already applies automatically under the name strength reduction, so hand-converting a multiplication in ordinary application code rarely buys anything today. Where it still matters is closer to the metal: fixed-point code targeting a core without a fast multiplier, and hardware datapaths such as FPGA or ASIC filter implementations, where the same minimal-signed-digit idea shows up again as the canonical signed digit (CSD) representation used to minimize the number of adders needed for a fixed multiplier coefficient.