algorithm - 2 ^ nはn-1未満の連続した乗算で計算できますか？

Question

n-1未満の連続した乗算で、任意のnが与えられた場合に2^nを計算する可能性に関する質問があります。n-1の乗算を行うタスクを回避することで、同じ操作を実現するために利用できる最善の戦略は何でしょうか。これはより少ない乗算で行うことができますか？はいの場合、どのように？

-ありがとう

Answer 1

はい、2^n は Log(n) 乗算で計算できます。これは、二乗による指数化として知られています。

Answer 2

(2^n) および (n>=0) の場合、ビットごとのシフトを使用できます: (2^n) は (1 << n) です。