快速加倍和fibonacci算法解释

Question

在研究矩阵幂运算时，我发现了快速加倍和下面的实现。我有以下问题：

1. 为什么for循环从31向下迭代到0？

2. 在条件中用i掩蔽n的目的是什么？

private static BigInteger Fibonacci(int n) {
BigInteger a = BigInteger.Zero;
BigInteger b = BigInteger.One;
for (int i = 31; i >= 0; i--) {
BigInteger d = a * (b * 2 - a);
BigInteger e = a * a + b * b;
a = d;
b = e;
if ((((uint)n >> i) & 1) != 0) {
BigInteger c = a + b;
a = b;
b = c;
}
}
return a;
}

请链接任何可以帮助我深入理解该主题的参考资料或文献。

干杯！

Answer 1

代码中循环的不变量是：

a = Fib(n/2^i)
b = Fib(n/2^i + 1)

(这里^是幂运算，而不是xor(。

通过使用快速加倍公式，您可以检查这些不变量在i变化时是否成立：

Fib(2k) = 2Fib(k)*Fib(k+1) - Fib(k)*Fib(k)
Fib(2k+1) = Fib(k+1)*Fib(k+1) + Fib(k)*Fib(k)

当n/2^i为奇数时，if语句应用公式：

Fib(2k+1), Fib(2k+2) = Fib(2k+1), Fib(2k) + Fib(2k+1)

(这只是常规的斐波那契公式(。

将代码视为这种递归代码的自上而下(而不是自下而上(版本可能会有所帮助：

def fib2(n):
if n == 0:
return 0, 1
a, b = fib2(n//2)
a, b = a*(b*2 - a), a*a + b*b
if n % 2 != 0:
a, b = b, a+b
return a, b

唯一显著的区别是，尽管此代码一直重复到n为0，但自上而下的代码总是迭代32次。

Answer 2

1. 为什么迭代器从31循环到0

答案。因为程序员用32位(从0到31(存储数据。范围从31到0的意义是从最低有效位迭代到最高有效位。

2. 条件中i掩蔽n的目的是什么

答案。这实际上并不是在掩饰。它是一个左移操作员。整体表达式if ((((uint)n >> i) & 1) != 0)检查数字n是否具有要添加到下一有效位中的奇偶校验位。

您要学习的主题称为位操作。以下是我第一次自学比特操作的一些资源。

• GeeksforGeeks-比特操作
• Codeburst博客-比特操作
• Leetcode博客文章-比特操作
• 第7章-位操作
• Interviewbit教程和问题-比特操作