下のビットから取り出して上へ積み、32 ビットを逆順にする

0 以上の整数を 32 ビットの並びとして見て、ビットの並びを左右逆にした数を返します。下のビットを 1 つずつ取り出し、答えを左へずらしながら積んでいく練習です。

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

問題

通信の機器が、ビットの並びを逆の順で送ってきます。受け取った整数 n を、上に 0 を補った 32 ビットの並びとして見て、並びを左右逆にした数を返す関数を書いてください。いちばん下のビットがいちばん上へ、いちばん上のビットがいちばん下へ移ります。

n は 0 以上 4294967295 (2 の 32 乗から 1 を引いた数) 以下です
答えも 0 以上 4294967295 以下の符号なしの整数で返します。いちばん上のビットが 1 でも、負の数にはしません

入力と出力の例

例 1

1 はいちばん下のビットだけが 1 です。逆にすると、いちばん上のビットだけが 1 の数、2 の 31 乗になります。

n = 1

2147483648

例 2

6 は下から 2 番目と 3 番目のビットが 1 です。逆にすると、上から 2 番目と 3 番目、つまり 2 の 30 乗と 2 の 29 乗の和です。

n = 6

1610612736

例 3

4096 は 2 の 12 乗です。下から 13 番目のビットは、逆にすると下から 20 番目、2 の 19 乗になります。

n = 4096

524288

面接での聞かれ方

面接では、ビットの取り出しと組み立てを確かめる問題として出されます。

「32 ビットの符号なし整数のビットを逆順にしてください」
「この関数を何度も呼ぶなら、速くできますか？」と続くことがあります
JavaScript で書くと、「いちばん上のビットが 1 のとき、負になりませんか？」と聞かれます

ずらす向きと回数、そして言語ごとの整数の扱いを正しく言えるかが見られています。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

数を 2 進の文字列に直し、32 桁に 0 で埋めて逆にし、数に戻す書き方もあります。正しく動きますが、ビット演算で書けるかを見る問題なので、数のままで組み立てます。

段 2

答え out を 0 から始めます。32 回、out を 1 ビット左へずらし、n のいちばん下のビット n & 1 を out に足し、n を 1 ビット右へずらします。最初に取り出した下のビットは、そのあと 31 回左へずらされて、いちばん上へ行きます。

段 3

n が途中で 0 になっても、回数は必ず 32 回にします。上の 0 も、逆にすると下の 0 として位を作るからです。JavaScript では、ビット演算の結果が 32 ビットの符号つき整数になるので、最後に >>> 0 で符号なしに戻します。

解答

Python

def reverse_bits(n):
    out = 0
    for _ in range(32):
        out = (out << 1) | (n & 1)
        n >>= 1
    return out

JavaScript

function reverseBits(n) {
  let out = 0;
  for (let k = 0; k < 32; k++) {
    out = (out << 1) | (n & 1);
    n >>>= 1;
  }
  return out >>> 0;
}

Go

func reverseBits(n uint32) uint32 {
	var out uint32
	for k := 0; k < 32; k++ {
		out = out<<1 | n&1
		n >>= 1
	}
	return out
}

Python の整数には上の限りが無いので、32 回で止めれば 32 ビットより大きくなりません。Go は uint32 で受けて返すので、ずらしてはみ出したビットは消えます。

計算量

時間は O(1) です。いつもちょうど 32 回まわります
使う記憶は O(1) です
何度も呼ぶなら、8 ビットの 256 通りを逆にした表を先に作り、4 つに分けて表を引いて組み直すと、ループが 4 回で済みます

よくある間違い

n が 0 になったら止める。 例 1 で 1 回目のあと n が 0 になり、out が 1 のままです。上の 0 も位を作るので、必ず 32 回まわします
JavaScript で符号なしに戻さない。 例 1 の答えは、out << 1 の結果として -2147483648 になります。最後に >>> 0 を付けます
JavaScript で n >>= 1 と書く。 符号つきでずらすので、n が 2147483648 以上だと上から 1 が入り続けます。>>>= を使います
ずらす向きを逆にする。 out を右へ、n を左へずらすと、並びは逆になりません。答えは左へ、受け取った数は右へずらします

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

main.py

def reverse_bits(n: int) -> int:
    """
    Goal: 何を返すか

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

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

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


# 「実行」を押すと、この行の結果が出ます
print(reverse_bits(1))

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