C++で[0, n]の範囲にセットビットがちょうど1つだけある数の個数を求める方法

問題概要

ある整数が与えられたとき、0からその数までの範囲（0〜num）に含まれる「セットビットがちょうど1つだけ」の数の個数を求めるのが本記事のテーマです。

セットビットとは、2進数表現において「1」となっているビットのことです。整数値を2進数に変換すると、必ず0と1の組み合わせで表されます。コンピュータの分野では、この「1」のことをセットビットと呼びます。

入力例・出力例

入力： int num = 15

出力： [0, 15] の範囲でセットビットが1つだけある数の個数は 4

解説： 与えられた数は15なので、対象となる範囲は0〜15です。各数値を4桁の2進数で表すと次のようになります。

0  → 0000 = セットビット0個
1  → 0001 = セットビット1個
2  → 0010 = セットビット1個
3  → 0011 = セットビット2個
4  → 0100 = セットビット1個
5  → 0101 = セットビット2個
6  → 0110 = セットビット2個
7  → 0111 = セットビット3個
8  → 1000 = セットビット1個
9  → 1001 = セットビット2個
10 → 1010 = セットビット2個
11 → 1011 = セットビット3個
12 → 1100 = セットビット2個
13 → 1101 = セットビット3個
14 → 1110 = セットビット3個
15 → 1111 = セットビット4個

この中でセットビットがちょうど1つであるのは 1, 2, 4, 8 の4つです。

入力： int num = 4

出力： [0, 4] の範囲でセットビットが1つだけある数の個数は 3

解説： 範囲は0〜4となり、セットビットが1つだけの数は 1, 2, 4 の3つです。

アプローチ①：素朴な方法（ナイーブ法）

まずは最も直感的な方法から見ていきましょう。範囲内のすべての数についてセットビットの数を実際に調べるアプローチです。

• 数値を入力し、処理用の関数に渡します。
• 該当する数の個数を格納するための一時変数 count を用意します。
• i = 1 から number までforループを回します。
• ループ内で __builtin_popcount(i) を呼び出し、i のセットビットの数を取得します。この関数はGCC系コンパイラで利用可能な組み込み関数で、引数の2進表現における1の個数を返します。
• 結果が1であれば count をインクリメントします。
• ループ終了後、count を返し、結果を出力します。

この方法の計算量は O(n log n) となります。n が大きくなると処理時間が伸びる点が難点です。

サンプルコード（ナイーブ法）

#include <iostream>
using namespace std;
// [0, n] の範囲でセットビットが1つだけある数を数える関数
int set_bits(int number){
    int count = 0;
    for (int i = 1; i <= number; i++){
        int temp = __builtin_popcount(i);
        if (temp == 1){
            count++;
        }
    }
    return count;
}
int main(){
    int number = 15;
    cout<<"[0, "<<number<<"] の範囲でセットビットが1つだけある数の個数: "<<set_bits(number);
    return 0;
}

出力結果

[0, 15] の範囲でセットビットが1つだけある数の個数: 4

アプローチ②：効率的な方法（O(log n)）

ここで重要な性質に気づきます。セットビットがちょうど1つだけある数は、必ず2のべき乗（1, 2, 4, 8, 16, ...）だということです。2進数で1が1箇所しかないということは、その位置に応じた2のべき乗に他なりません。

この性質を利用すれば、number 以下の2のべき乗の個数を数えるだけで答えが求まります。計算量は O(log n) に大幅に改善できます。

• 数値を入力し、処理用の関数に渡します。
• カウント用変数 count を用意します。
• temp を1で初期化し、temp ≤ number の間whileループを回します。
• ループ内では count を1増やし、temp を2倍していきます。
• ループを抜けたら count を返し、結果を出力します。

サンプルコード（効率的な方法）

#include <iostream>
using namespace std;
// [0, n] の範囲でセットビットが1つだけある数を数える関数
int set_bits(int number){
    int count = 0;
    int temp = 1;
    while(temp <= number){
        count++;
        temp = temp * 2;
    }
    return count;
}
int main(){
    int number = 15;
    cout<<"[0, "<<number<<"] の範囲でセットビットが1つだけある数の個数: "<<set_bits(number);
    return 0;
}

出力結果

[0, 15] の範囲でセットビットが1つだけある数の個数: 4

まとめ

セットビットが1つだけの数は2のべき乗に等しいという性質を利用すると、全数を走査する O(n) のナイーブ法から、O(log n) の効率的なアルゴリズムへと改善できます。大きな入力値を扱う場合や競技プログラミングでは、後者のアプローチを選ぶことで大幅な高速化が期待できるでしょう。