C++でk個のセットビットを持つ数を最大化するために必要な最小フリップ回数

問題文

2つの整数 n と k が与えられます。n のビットを反転（フリップ）して、結果の数がちょうど k 個のセットビット（値が1のビット）を持ち、かつ取り得る最大の数になるようにするために必要な、最小のフリップ回数を求めてください。なお、入力は「k が n のビット数より小さい」という条件を満たす必要があります。

例

• n = 9、k = 2 とします。
• 9 の2進表現は 1001 であり、4ビットで構成されています。
• 4桁の2進数の中でセットビットが2個となる最大の数は 1100、すなわち10進数の 12 です。
• 1001 を 1100 に変換するには、2ビットを反転する必要があります。

アルゴリズム

1. n のビット数を数えます。これを bitCount とします。math ライブラリの log2 関数を次のように使って求められます:
    bitCount = log2(n) + 1;
2. セットビットが k 個ある最大の数を求めます: maxNum = pow(2, k) - 1;
3. セットビットが k 個あり、かつ n と同じビット数を持つ最大の数を求めます:
    maxNum = maxNum << (bitCount - k);
4. (n ^ maxNum) を計算し、そのセットビットの数を数えます。

考え方のポイント

数を最大化するには、セットビットをできるだけ上位の桁に集めるのが最適です。そこで、最上位ビットから順に k 個の1を並べた理想の数 maxNum を作り、元の数 n との XOR を取ります。XOR の結果には「n と maxNum で異なるビット」だけが1として現れ、これはまさに反転が必要なビットを意味します。したがって、XOR 結果のセットビット数を数えれば、それがそのまま最小フリップ回数となります。

C++での実装例

#include <iostream>
#include <cmath>
using namespace std;
int getSetBits(int n){
    int cnt = 0;
    while (n) {
        ++cnt;
        n = n & (n - 1);
    }
    return cnt;
}
int minFlipsRequired(int n, int k){
    int bitCount, maxNum, flipCount;
    bitCount = log2(n) + 1;
    maxNum = pow(2, k) - 1;
    maxNum = maxNum << (bitCount - k);
    flipCount = n ^ maxNum;
    return getSetBits(flipCount);
}
int main(){
    cout << "Minimum required flips: " << minFlipsRequired(9, 2) << "\n";
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Minimum required flips: 2