繰り返し 2 乗で掛ける回数を減らし、x の n 乗を求める

小数 x と、負もありうる整数 n から、x の n 乗を求めます。n を 2 進で見て、x を 2 乗し続けながら 1 のビットの所だけ掛ければ、掛け算の回数が n の桁の数ほどで済む練習です。

海外で定番の問題リスト 4 本には入っていません

問題

数を扱う道具に、累乗の計算を入れます。小数 x と整数 n を受け取り、x の n 乗を返す関数を書いてください。言語に備わった累乗の関数や演算子 (**、Math.pow、math.Pow) は使わず、掛け算と割り算だけで求めます。

n が 0 なら 1 を返します
n が負なら、x の -n 乗の逆数を返します。このとき x は 0 ではありません
x は -100 より大きく 100 より小さい数、n は -2147483648 以上 2147483647 以下です
答えの絶対値は 10000 以下に収まるものとします

入力と出力の例

例 1

0.5 を 3 回掛けて 0.125 です。

x = 0.5 n = 3

0.125

例 2

負の数を奇数回掛けると、負になります。

x = -2 n = 5

-32

例 3

n が負なので、4 の 2 乗 (16) の逆数です。

x = 4 n = -2

0.0625

面接での聞かれ方

面接では、短い問題文に端の場合がいくつも隠れている問題として出されます。

「pow(x, n) を自分で書いてください」
1 回ずつ掛ける書き方を見せると、「n が 20 億だったら？」と聞かれます
「n が負のときは？」「n がいちばん小さい負の数のときに、符号を反転できますか？」と、端の場合を詰められます

芯は、掛ける回数を n 回から log n 回に減らす考え方です。分割統治の入り口として、ほかの問題の土台にもなります。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に x を n 回掛ける書き方は、n が 20 億を超えると、掛け算が 20 億回を超えて間に合いません。

段 2

x¹³ は、13 を 2 進で書いた 1101 を使うと、x⁸ × x⁴ × x¹ に分けられます。x、x²、x⁴、x⁸ は、1 つ前を 2 乗するだけで次々に作れます。そこで、base を x から始めて毎回 2 乗し、n のいちばん下のビットが 1 のときだけ答えに掛け、n を 1 ビット右へずらします。

段 3

n が負なら、先に x を 1 / x に置き換え、n を -n にしてから同じことをします。n が -2147483648 のとき、-n は 32 ビットの符号つき整数に入りません。Python と JavaScript の数、Go の int (64 ビット) なら入るので、そのまま反転できます。32 ビットの整数しか無い言語では、64 ビットの型に移してから反転します。

解答

Python

def fast_power(x, n):
    if n < 0:
        x = 1 / x
        n = -n
    out = 1.0
    base = x
    while n > 0:
        if n & 1:
            out *= base
        base *= base
        n >>= 1
    return out

JavaScript

function fastPower(x, n) {
  if (n < 0) {
    x = 1 / x;
    n = -n;
  }
  let out = 1;
  let base = x;
  while (n > 0) {
    if (n % 2 === 1) {
      out *= base;
    }
    base *= base;
    n = Math.floor(n / 2);
  }
  return out;
}

Go

func fastPower(
	x float64, n int,
) float64 {
	if n < 0 {
		x = 1 / x
		n = -n
	}
	out := 1.0
	base := x
	for n > 0 {
		if n&1 == 1 {
			out *= base
		}
		base *= base
		n >>= 1
	}
	return out
}

JavaScript の & と >> は 32 ビットの整数として計算するので、n が 2147483648 のときに壊れます。そこで % 2 と 2 で割った商を使っています。3 つの言語とも、掛ける順は同じです。

計算量

時間は O(log n) です。1 回まわるごとに n が半分になり、n が 20 億でも 32 回ほどで終わります
使う記憶は O(1) です。out と base だけです
再帰で「n が偶数なら x^(n/2) を 2 乗、奇数ならさらに x を掛ける」と書いても同じ O(log n) ですが、呼び出しの深さの分 O(log n) の記憶を使います

よくある間違い

1 回ずつ掛ける。 n が大きいと間に合いません。n が 2147483647 なら、掛け算を 20 億回します
負の n を忘れる。 例 3 で、while n > 0 に一度も入らず 1 を返してしまいます。先に逆数と符号の反転をします
32 ビットの整数で -n を作る。 n が -2147483648 だと、反転しても 32 ビットに入らずあふれます。64 ビットの型に移してから反転します
JavaScript でビット演算を使う。 n >> 1 は n を 32 ビットに切るので、n が 2147483648 のとき負になって繰り返しがすぐ終わります

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def fast_power(x: float, n: int) -> float:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(fast_power(0.5, 3))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します