Multiply an Integer by 7 Without the Multiplication Operator
Give a fast way to compute $7x$ for an integer $x$ without using the multiplication operator (no *, and no loop that adds $x$ seven times). Explain why it works and what can go wrong.
Hints
- Shifting a binary number left by $k$ positions multiplies it by $2^k$.
- Write $7$ as a combination of powers of two: $7 = 8 - 1$, or $7 = 4 + 2 + 1$.
- $(x \ll 3) - x$ is one shift and one subtraction. Think about what happens when $8x$ does not fit in the integer type even though $7x$ would.
Worked Solution
How to Think About It: Multiplication by a power of two is free (a shift), and $7$ is one less than a power of two. So build $8x$ with a shift and subtract $x$ once.
Approach: Use $7x = 8x - x = (x \ll 3) - x$, or equivalently $(x \ll 2) + (x \ll 1) + x$; verify on a range of integers and analyze overflow.
Formal Solution:
*Step 1 -- Shifts as multiplication.* For a nonnegative integer $x = \sum_i b_i 2^i$, the left shift $x \ll k$ produces $\sum_i b_i 2^{i+k} = 2^k x$. In two's complement the same identity holds for negative values as long as the result fits in the type (arithmetically; in C the left shift of a negative signed value is formally undefined, so use unsigned or a wider type).
*Step 2 -- Decompose $7$.* $7 = 2^3 - 1$, so $$7x = 8x - x = (x \ll 3) - x.$$ This costs one shift and one subtraction. The alternative $7 = 4 + 2 + 1$ gives $(x \ll 2) + (x \ll 1) + x$, two shifts and two additions, slightly more work but with a smaller largest intermediate ($4x$ rather than $8x$).
*Step 3 -- Correctness check.* $(x \ll 3) - x = 7x$ was verified for every integer $x \in [-10^4, 10^4]$ in Python (arbitrary-precision integers, so no overflow).
*Step 4 -- Overflow.* In a $w$-bit type the intermediate $8x$ needs one more bit than $7x$ (roughly): for signed 32-bit integers, $x = 2^{29}$ gives $7x = 3{,}758{,}096{,}384 > 2^{31} - 1$, so the true product overflows anyway; but there is also a range where $7x$ fits and $8x$ does not, for example $x = 2^{28} + 1$: $7x = 1{,}879{,}048{,}199$ fits, while $8x = 2^{31} + 8$ does not. In unsigned (wraparound) arithmetic the final answer is still correct modulo $2^w$ because subtraction undoes the wrap; in signed arithmetic in C it is undefined behaviour. Use a wider intermediate type or x * 7 and let the compiler do the strength reduction.
```python def times7(x: int) -> int: return (x << 3) - x
assert all(times7(x) == 7 * x for x in range(-10_000, 10_001)) ```
Answer: $7x = (x \ll 3) - x$: shifting left by $3$ multiplies by $8$, then subtract $x$ once. Equivalently $(x \ll 2) + (x \ll 1) + x$. Watch for overflow of the intermediate $8x$ in fixed-width types (and undefined behaviour when shifting negative signed values in C).
Intuition
In binary, appending $k$ zeros multiplies by $2^k$, so $8x$ is a single shift and $7x = 8x - x$ is a shift and a subtraction, both single-cycle operations. This is exactly the strength reduction that optimizing compilers perform for multiplication by small constants (on x86 they may even use a single lea), and it is why hand-written *7 is never slower in practice. The interview value is in the follow-up: the intermediate $8x$ can overflow a fixed-width type even when $7x$ fits, and left shifts of negative signed integers are undefined in C, so the trick trades safety for speed unless you reason about the bit widths.