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.

## Natural numbers as sums of powers of two

You can express any natural number as a sum of powers of two. In fact, that’s what a number in binary notation is. The value of a sequence of

*n* binary digits

*d*_{i}
d_{n-1}d_{n-2} ... d_{0}

is the sum

∑_{0 ≤ i < n} d_{i} × 2^{i}
= d_{0} × 1 + d_{1} × 2 + d_{2} × 4 + ...

Each digit

*d*_{i} is either one or zero. Therefore, each addend is either a power of two or it is zero.

## The algorithm

Roughly, the algorithm iterates over the digits starting with

*d*_{0}. After each iteration, it doubles

`str`, the string to repeat. If the current digit is one then the current value of

`str` is added to the result. In other words, if the digit

*d*_{i} is one,

*2*^{i} times

`str` is added to the result. The algorithm,

implemented in JavaScript and slightly edited, looks as follows.

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 log_{2}(`num`) steps. As an aside, concatenating strings via the plus operator (`+`) has become fast on modern JavaScript engines [3].

## ECMAScript 6’s String.prototype.repeat()

ECMAScript 6 will have a string method

`String.prototype.repeat()` that produces the same results as the function

`stringRepeat`. Mathias Bynens has written a spec-compliant

polyfill that uses an algorithm similar to

`stringRepeat`’s.

## References

- Binary bitwise operators in JavaScript
- Integers and shift operators in JavaScript
- String concatenation in JavaScript