algorithm - 可以用少于 n-1 次连续乘法计算 2^n 吗？

Question

我有一个问题与计算 2^n 的可能性有关，给定任何 n，小于 n-1 次连续乘法。通过避免执行 n-1 乘法的任务，我可以用来实现相同操作的最佳策略是什么？这可以在较小的乘法中完成吗？如果是，那么如何？

-谢谢

Answer 1

对于 (2^n) 和 (n>=0) 您可以使用按位移位：(2^n) 是 (1 << n)

Answer 2

是的 2^n 可以在 Log(n) 乘法中计算，这被称为Exponentiation by squareing。