O(log(n)) の String.prototype.repeat (JavaScript)

C言語歴が無いものでbit演算を殆ど使った事が無かったから。冪乗のalgorithmだ。JavaScriptの整数値は最大で32bit (桁) しか無いけどね。

String.prototype.repeat = function (times) {
  var r;

  if (times <= 0) { return ''; }
  r = this.repeat(times >> 1);
  r += r;
  if (times & 1) { r += this; }
  return r;
};

console.log('w'.repeat(0) === '');
console.log('w'.repeat(1) === 'w');
console.log('w'.repeat(2) === 'ww');
console.log('w'.repeat(3) === 'www');
console.log('w'.repeat(4) === 'wwww');
console.log('w'.repeat(5) === 'wwwww');
console.log('w'.repeat(6) === 'wwwwww');
console.log('w'.repeat(7) === 'wwwwwww');
console.log('w'.repeat(8) === 'wwwwwwww');

昔に此れで読んだ。記事出た直後に読んだので、多分五年前に読んだ。
cf. 404 Blog Not Found:アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法 http://blog.livedoor.jp/dankogai/archives/51172176.html
まあ最適化にもよるが再帰より繰り返しの方が速い。またいつか忘れた頃にやる。