C++でNを除算したとき、商より多くのセットビットを持つ除数の個数を求める

整数 N が与えられます。ここでの課題は、1 から N までの各整数で N を順に割っていき、割る数（除数）のセットビット数が、そのときの商のセットビット数以上になるケースが何回あるかを数えることです。

例で理解する

例 1

入力: int N = 6

出力: N を除算したとき、商以上のセットビットを持つ除数の個数: 5

説明: まず N を 1〜N の各数で割り、除数と商それぞれのセットビット数を比較します。

• 1 → 6 ÷ 1(1) = 6(2) … 1 ＜ 2 → 対象外
• 2 → 6 ÷ 2(1) = 3(2) … 2 ＝ 2 → 対象
• 3 → 6 ÷ 3(2) = 2(1) … 2 ＞ 1 → 対象
• 4 → 6 ÷ 4(1) = 1(1) … 1 ＝ 1 → 対象
• 5 → 6 ÷ 5(2) = 1(1) … 2 ＞ 1 → 対象
• 6 → 6 ÷ 6(2) = 1(1) … 2 ＞ 1 → 対象

このうち「対象」となるケースを数えると、出力は 5 になります。

例 2

入力: int N = 10

出力: N を除算したとき、商以上のセットビットを持つ除数の個数: 8

説明: 同様に、N を 1〜N の各数で割って比較していきます。

• 1 → 10 ÷ 1(1) = 10(2) … 1 ＜ 2 → 対象外
• 2 → 10 ÷ 2(1) = 5(2) … 2 ＝ 2 → 対象
• 3 → 10 ÷ 3(2) = 3(2) … 2 ＝ 2 → 対象
• 4 → 10 ÷ 4(1) = 2(1) … 1 ＜ 2 → 対象外
• 5 → 10 ÷ 5(2) = 2(1) … 2 ≥ 2 → 対象
• 6 → 10 ÷ 6(2) = 1(1) … 2 ＞ 1 → 対象
• 7 → 10 ÷ 7(3) = 1(1) … 3 ＞ 1 → 対象
• 8 → 10 ÷ 8(1) = 1(1) … 1 ＝ 1 → 対象
• 9 → 10 ÷ 9(2) = 1(1) … 2 ≥ 2 → 対象
• 10 → 10 ÷ 10(2) = 1(1) … 2 ＞ 1 → 対象

対象となるケースを数えると、出力は 8 になります。

プログラムで使用しているアプローチ

• 正の整数 N を入力として受け取り、関数 divisors_quotient() に引数として渡します。
• divisors_quotient() の内部では「N − set_quo(N) + 1」を返します。境界値の特定は set_quo() が担います。
• set_quo() の内部では次の処理を行います。
  • 一時変数 start と end を用意し、start を 1、end を √N で初期化します。
  • start ＜ end の間ループを続け、毎回 temp = (start + end) / 2 を計算します。
  • verify(temp, N) が真を返せば end = temp、そうでなければ start = temp + 1 とします（いわゆる二分探索です）。
  • ループ終了後、verify(start, N) が偽であれば start + 1 を、真であれば start を返します。
• verify() の内部では、val_bit(temp / val) の結果が val_bit(val) の結果以下であれば true、そうでなければ false を返します。
• val_bit() の内部では、結果を格納する変数 count を宣言し、val が 0 になるまで val を 2 で割りながら count を 1 ずつ増やし、最後に count を返します。

このアプローチのポイント

N を 1 から順にすべて試すと計算量は O(N) になりますが、小さい側の除数と大きい側の商には対称性があるため、二分探索で「条件が成り立たなくなる境界」を絞り込めば、比較回数を対数オーダーまで減らせます。これにより、N が大きい場合でも効率的に答えを求められます。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

int val_bit(int val) {
    int count = 0;
    while (val) {
        val = val / 2;
        count++;
    }
    return count;
}
bool verify(int val, int temp) {
    if (val_bit(temp / val) <= val_bit(val)) {
        return true;
    }
    return false;
}
int set_quo(int N) {
    int start = 1;
    int end = sqrt(N);
    while (start < end) {
        int temp = (start + end) / 2;
        if (verify(temp, N)) {
            end = temp;
        } else {
            start = temp + 1;
        }
    }
    if (!verify(start, N)) {
        return start + 1;
    } else {
        return start;
    }
}

int divisors_quotient(int N) {
    return N - set_quo(N) + 1;
}
int main() {
    int N = 10;
    cout << "Count of divisors having more set bits than quotient on dividing N are: " << divisors_quotient(N);
    return 0;
}

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

出力

Count of divisors having more set bits than quotient on dividing N are: 8