javascript - for i in bin(n)[3 :]: in Javascript? 等价于什么

Question

我正在研究一种返回大斐波那契数模的算法。我找到了一种快速、高效的算法来使用以下 python 确定值:

def fib(n):
    v1, v2, v3 = 1, 1, 0    # initialise a matrix [[1,1],[1,0]]
    for rec in bin(n)[3:]:  # perform fast exponentiation of the matrix (quickly raise it to the nth power)
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec == '1':    
            v1, v2, v3 = v1+v2, v1, v2
    return v2 

我很想了解如何在 JavaScript 中实现这一点，但二进制转换线让我很困惑。 这里 for 循环使用每个整数的二进制转换，我假设从 0 到 n，并将结果 chop 到 3 位。循环体内还针对 1 的字符串表示形式对“rec”进行了相等性检查。有人可以打破这个吗？任何见解都值得赞赏。谢谢!

Answer 1

这是 JavaScript (ES6) 的等效项:

function fib(n) {
    let [v1, v2, v3] = [1, 1, 0]; // initialise a matrix [[1,1],[1,0]]
    for (i of (n).toString(2).slice(1)) {  // perform fast exponentiation of the matrix (quickly raise it to the nth power)
        let calc = v2*v2;
        [v1, v2, v3] = [v1*v1+calc, (v1+v3)*v2, calc+v3*v3];
        if (i === '1')
            [v1, v2, v3] = [v1+v2, v1, v2];
    }
    return v2;
}

// Demo
console.log(fib(15));

Python 和 JavaScript 版本之间的差异:

当 Python bin() 函数生成带有“0b”前缀的字符串时，JavaScript toString(2) 方法将生成不带该前缀的字符串。由于 python 代码随后会从中删除前 3 个字符(使用 [3:])，因此 JavaScript 等效项应该只删除一个字符(使用 slice(1) 或 substr(1))。

Python 多重赋值在 JavaScript 中转换为解构赋值，这需要数组文字表示法。

Python for 循环中使用的 in 会转换为 JavaScript (ES6) 中的 of。 JavaScript 也知道 in 语法，但这有不同的含义:i 然后将采用索引值(从 0 开始，然后逐一递增)而不是该索引处的字符内容。

在Python中==执行严格的比较。在 Javascript 中，需要使用 === 进行严格比较，尽管在本例中它也可以使用 == (非严格比较，其中 1 被视为相等与“1”)，最好的做法是尽可能使用 ===。

关于算法

请注意，二进制转换仅发生一次:只有 n 被转换为二进制字符串。该算法不需要该二进制表示的第一个数字(它始终是 1，除非 n 为零)。因此该数字(和“0b”前缀)被从中删除。所以它并不是将该字符串 chop 为 3 个字符——不，它删除了前三个字符，即“0b1”(或当 n 为零时为“0b0”)被抛出窗口。

然后i获取剩余的零和一字符串中每个字符的值。因此，在每次迭代中，i 要么是“0”，要么是“1”。名称选择 i 不是最好的:传统上 i 用于整数，而不是字符，但在此代码中它是一个字符。