C++でn個のセットビットとm個のアンセットビットを持つ最大の数を求める方法

この記事では、2つの整数値 n と m が与えられたとき、2進数表現において n 個のセットビット（1）と m 個のアンセットビット（0）を持つ最大の数を求める方法について解説します。

問題の理解

まず、具体的な例で問題を確認してみましょう。

入力 : n = 3, m = 1
出力 : 14

説明：

最大の数になるのは、上位に3つのセットビットが並び、その下位に1つのアンセットビットが続くパターンです。

(1110)2 = 14

解法アプローチ

この問題へのシンプルなアプローチは、まず (n + m) 個すべてのビットがセットされた数を作成し、そこから下位（LSB側）の m ビットをオフにするというものです。

(n + m) 個のセットビットを持つ数は、次の式で簡単に生成できます。

$$(1\ll(n+m))-1$$

さらに、下位 m ビットだけがセットされたマスク値 $$(1\ll m)-1$$ を用意し、元の数とXOR演算を行うことで、下位 m ビットを反転（0に）できます。これにより、上位 n ビットが1、下位 m ビットが0となる最大の数が得られます。

実装例

上記のソリューションの動作を示すC++プログラムは以下の通りです。

#include <iostream>
using namespace std;
int findlargestNumber(int n, int m){
   int maxNum = (1 << (n + m)) - 1;
   if (m == 0)
      return maxNum;
   int number = (1 << m) - 1;
   return (maxNum ^ number);
}
int main(){
   int n = 5,
   m = 2;
   cout<<"The largest number with "<<n<<" set bits and "<<m<<" unset bits is "<<findlargestNumber(n, m);
   return 0;
}

出力

The largest number with 5 set bits and 2 unset bits is 124

コードの解説

• (1 << (n + m)) - 1 ： 下位 (n + m) ビットがすべて1になった数を生成します。
• (1 << m) - 1 ： 下位 m ビットだけが1になったマスク値を生成します。
• XOR演算（^）によって、maxNum の下位 m ビットが0に切り替わり、目的の数が完成します。

m が 0 の場合は、すべてのビットがセットされた状態がそのまま答えになるため、maxNum をそのまま返しています。

計算量

• 時間計算量： O(1) ― ビット演算のみで構成されるため定数時間で処理できます。
• 空間計算量： O(1) ― 追加のメモリは不要です。