Recently, Michael Ficarra pointed me to an efficient algorithm for repeating a string several times. In this blog post, I explain how it works.
The algorithm makes use of the fact that natural numbers (non-negative integers) can be represented as sums of powers of two.
dn-1dn-2 ... d0is the sum
∑0 ≤ i < n di × 2i = d0 × 1 + d1 × 2 + d2 × 4 + ...Each digit di is either one or zero. Therefore, each addend is either a power of two or it is zero.
function stringRepeat(str, num) { num = Number(num); var result = ''; while (true) { if (num & 1) { // (1) result += str; } num >>>= 1; // (2) if (num <= 0) break; str += str; } return result; }In line 1, the bitwise And operator (&) [1] is used to extract the value of the digit at the current position. In line 2, the bitshift operator (>>>) [2] is used to shift the next digit to the least significant (rightmost) position.
Where a naive algorithm takes num steps to produce a result, this algorithm takes log2(num) steps. As an aside, concatenating strings via the plus operator (+) has become fast on modern JavaScript engines [3].