高速に同じ文字を繰り返し入力するときのアルゴリズム

404 Blog Not Foundで同じ文字を高速に繰り返し入力する際のアルゴリズムが公開されています。





コードは以下となります。

function (str, n){
    var result = '';
    for(n *= 1; n > 0; n >>>= 1, str += str) if (n & 1) result += str;
    return result;
}

コードの説明をすると、

for(n *= 1; n > 0; n >>>= 1, str += str)

がミソですね。

n >>>= 1

で、繰り返し入力したい文字列の個数であるnが半分になります。


そして、

str += str

で、現在繰り返し入力した文字列の個数が倍となります。

そして、

if (n & 1) result += str;

で、最後に2で割り切れなかった場合繰り返し文字列を1つ足して終了します。


要は、元となる数字を半分にしながら、繰り返す文字を倍にしていって、数字が1になったら最後にもう一個繰り返す文字を足すということをやっているコードだと思います。
# 間違っていたらどなたか突っ込んでください。



とてもきれいなコードですね。
こんなコードを簡単に書けるようになりたいものです。



高速に同じ文字を繰り返し入力するときのアルゴリズム - アルゴリズム - 同じ文字列のn回繰り返しをlog n回で作る方法