algorithm - 通过循环移位求幂

Question

这里关于 SO 的其他一些主题提到了论文“Fast Exponentiation with Precomputation ”由 Brickell 等人撰写，其中连同二进制数字对应的幂的预计算的简单概念，有一个关于“通过循环移位求幂”的陈述(据我所知)。不幸的是，论文的那部分是以非常笼统的形式表达的，所以我根本无法弄清楚他们是否在谈论一些明显的东西，这些东西会随着 2**n 以外的其他基数变得复杂，或者真的存在一些其他的求幂方法比乘法(平方)？

例如，假设我们有 x = 5 (这是二进制的 00101)。怎么可能以y = 5 * 5结束？ (即二进制形式的 11001)，仅使用位移和一些加法？当然，该算法应该比乘法更有效——答案“你可以通过一堆位移和加法来模拟每个乘法，如 y = (5 << 2) + (5 << 0) ”不算。好吧，它可以计算稀疏数字是否常见，但这不是常见情况，并且确定确切的位填充计数也很耗时，因此，除非数字非常稀疏，否则它不是值得尝试，每次平方后都需要进行新的评估。

Answer 1

该方法称为“二进制分解求幂”，您可以在 Knuth 4.6.3 中找到相关讨论。例如， ，因此在第一种情况下你需要 7 次乘法，但在第二种情况下需要 3 次(注意 8 = 100 在二进制中)。执行此操作的代码如下:

long power( int x, int n ){
   long result = 1;
   long base = x;
   while( true ){
      if( n & 1 ) result = base * result;
      n = n >> 1;
      if( n == 0 ) return result;
      base = base * base;
   }
}