Pythonで同じセットビット数を持つ次に大きい数を見つけるプログラム

数値 n が与えられたとき、2進表現における1の個数（セットビット数）が n と同じで、かつ n より大きい最小の数を求める問題を考えます。

例えば、入力が n = 7 の場合、出力は 11 になります。7 を2進数で表すと「0111」ですが、1が3つという条件を保ったまま 7 より大きい最小の数は、2進数で「1011」、すなわち10進数の 11 だからです。

解法のアプローチ

この問題はビット操作を利用することで効率的に解けます。手順は以下の通りです。

• copy に n を代入し、zeros と ones を 0 で初期化します。

• copy が 0 ではなく偶数である間、次の処理を繰り返します。

  • zeros を 1 増やす

  • copy を 1 ビット右シフトする（copy / 2 と同等）

• copy が奇数である間、次の処理を繰り返します。

  • ones を 1 増やす

  • copy を 1 ビット右シフトする（copy / 2 と同等）

• right := ones + zeros とします。

• n := n OR (2^right) — right 番目のビットを 1 にセットします。

• n := n AND NOT((2^right) − 1) — right より下位のビットをすべてクリアします。

• n := n OR ((2^(ones − 1)) − 1) — 下位 ones − 1 ビットをすべて 1 にセットします。

• n を返します。

仕組みのポイント

このアルゴリズムの核心は、2進表現の中で最も右側にある「01」というパターンを「10」へ入れ替える点にあります。こうすることで、1の総数を変えずに数を大きくできます。その後、残りの1を可能な限り下位のビットへ寄せることで、「同じ1の個数を持ちながら、元の数より大きい最小の数」が得られます。

計算量はビット長に比例する O(log n) となり、全ての候補を順に調べる方法よりもはるかに効率的です。

実装例

class Solution:
    def solve(self, n):
        copy = n
        zeros = 0
        ones = 0
        while copy and not copy & 1:
            zeros += 1
            copy >>= 1
        while copy & 1:
            ones += 1
            copy >>= 1
        right = ones + zeros
        n |= 1 << right
        n &= ~((1 << right) - 1)
        n |= (1 << ones - 1) - 1
        return n

ob = Solution()
n = 7
print(ob.solve(n))

入力

7

出力

11