[2014-01-29] bitwise_ops, dev, javascript, jslang

(Ad, please don’t block)

Recently, Michael Ficarra pointed me to an efficient algorithm for repeating a string several times. In this blog post, I explain how it works.
## 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*_{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.
`&`) [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.
## 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

The algorithm makes use of the fact that natural numbers (non-negative integers) can be represented as sums of powers of two.

dis the sum_{n-1}d_{n-2}... d_{0}

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

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 (

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].