在研究矩阵求幂时，我遇到了快速加倍和下面的实现。我有以下问题：
为什么for循环从31迭代到0？
在条件中被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;
}
请链接所有可以帮助我深入理解该主题的参考文献或文献。
干杯！
代码中循环的不变性是：
a = Fib(n/2^i)
b = Fib(n/2^i + 1)
（这里^是幂而不是xor）。
您可以使用快速倍增公式来检查这些不变式是否随我的变化而保持：
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次。
答案因为程序员将数据存储为32位（范围从0到31）。从31到0的含义是从最低有效位到最高有效位进行迭代。
答案那实际上不是掩盖。它是左移运算符。整体表达式if ((((uint)n >> i) & 1) != 0)检查数字n是否在下一个有效位中添加一个奇偶校验位。
您要学习的主题称为位操作。这里是我最初自学比特操作的一些资源。