Times seven using shifts and subtraction

Question

How can an integer $x$ be multiplied by $7$ quickly without using the multiplication operator?

Short answer

Compute (x << 3) - x. Shifting left by $3$ bits multiplies by $8$ , and $8x-x=7x$ . Shifts and subtractions are single cheap instructions; overflow behaves as with ordinary multiplication.

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 7.2 The Power of Two, 'Multiplication by 7', p.181; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Algorithms, Growth Rates, and Asymptotic Notation
Quicksort and Randomized Quicksort