C++で最大K個のセットビットを持つX未満の最大数を求める方法

このチュートリアルでは、与えられた整数 x 以下で、セットビット（2進数表記において1になっているビット）の数が最大 k 個となる最大の数を求めるプログラムをC++で作成します。

問題のポイント

セットビットとは、数値を2進数で表したときに値が1となっているビットのことです。例えば、65は2進数で「1000001」と表されるため、セットビットは2個あります。

解き方の手順

• 整数 x と k を初期化します。
• x のセットビットの数を求めます。
• セットビット数から k を引いた回数だけループを実行します。
  • 各ループで、x の値を x & (x - 1) で更新します。
• 最終的な x の値を返します。

x & (x - 1) という演算は、x の最下位にあるセットビットを0にする有名なビット操作テクニックです。この操作を繰り返し適用することで、セットビットの数を1つずつ減らし、条件を満たす最大の数を効率的に求めることができます。

実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int largestNumberWithKBits(int x, int k) {
   int set_bit_count = __builtin_popcount(x);
   if (set_bit_count <= k) {
      return x;
   }
   int diff = set_bit_count - k;
   for (int i = 0; i < diff; i++) {
      x &= (x - 1);
   }
   return x;
}
int main() {
   int x = 65, k = 2;
   cout << largestNumberWithKBits(x, k) << endl;
   return 0;
}

出力結果

上記のコードを実行すると、次のような結果が得られます。

65

この例では、65（2進数：1000001）のセットビットは2個であり、k = 2 以下の条件をすでに満たしているため、そのまま65が返されます。もし x のセットビット数が k を超えていた場合は、超過分だけ下位のセットビットが順にクリアされます。

まとめ

本チュートリアルでは、GCC拡張の __builtin_popcount 関数でセットビット数を取得し、x & (x - 1) の操作を繰り返すことで、セットビットが最大k個となる最大の数を効率よく求める方法を学びました。チュートリアルの内容についてご不明な点がある場合は、コメント欄でお気軽にお知らせください。