【C++】2進表現でセットビット数が奇数になる整数の個数を求める方法

整数 n が与えられたとき、1 から n までの整数の中に、2進表現した際のセットビット（1になっているビット）の数が奇数となるものがいくつあるかを求める問題を解説します。

具体例

入力

n = 10

出力

5

この場合、1 から 10 までの整数のうち、2進表現でのセットビット数が奇数になるものは 5 個あります。

アルゴリズム

• 整数 N を初期化します。

• 2進表現におけるセットビットの数を数える関数を作成します。

• カウント用の変数を 0 で初期化します。

• 1 から N まで繰り返すループを記述します。

  • 各整数についてセットビットの数を数えます。

  • セットビットの数が奇数であれば、カウントを 1 増やします。

• 最後にカウントを返します。

C++による実装

以下は、上記のアルゴリズムを C++ で実装したコードです。

#include <bits/stdc++.h>
using namespace std;
int getSetBitsCount(int n) {
   int count = 0;
   while (n) {
      if (n % 2 == 1) {
         count += 1;
      }
      n /= 2;
   }
   return count;
}
int getOddSetBitsIntegerCount(int n) {
   int count = 0;
   for (int i = 1; i <= n; i++) {
      if (getSetBitsCount(i) % 2 == 1) {
         count += 1;
      }
   }
   return count;
}
int main() {
   int n = 10;
   cout << getOddSetBitsIntegerCount(n) << endl;
   return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

5

補足：より効率的な実装

セットビットの数を数える処理は、n & (n - 1) を使うことで最下位のセットビットを1回ずつ消去でき、より高速にカウントできます。また、C++20 以降では標準ライブラリの std::popcount を利用することも可能です。