C++で指定された数値のセットビットから作れる最小の数を求める方法

問題の概要

符号なし整数が与えられたとき、その数値に含まれる「セットビット（1になっているビット）」だけを使って構成できる最小の数を求めます。

例

入力が 10 の場合、答えは 3 になります。

10 の2進表現は 1010 であり、セットビットは2つあります。2つのセットビットを持つ最小の数は 0011、すなわち 3 です。

アルゴリズム

1. 与えられた数値のセットビットの個数を数えます。
2. 2^(セットビット数) − 1 を計算した値が、求める最小の数になります。

たとえばセットビットが3個の場合は 2^3 − 1 = 7（2進数で 111）となります。セットビットをすべて下位の桁に集めた形が最も小さい数になるためです。

C++での実装例

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

// セットビットの個数を数える関数
int getSetBits(int n) {
    int cnt = 0;
    while (n) {
        ++cnt;
        n = n & (n - 1); // 最下位のセットビットを消していく
    }
    return cnt;
}

// セットビットから作れる最小の数を返す関数
int getMinNumber(int n) {
    int bits = getSetBits(n);
    return pow(2, bits) - 1;
}

int main() {
    int n = 10;
    cout << "Minimum number = " << getMinNumber(n) << endl;
    return 0;
}

上記のプログラムでは、n & (n - 1) というビット演算のテクニックを使うことで、ループごとに最下位のセットビットを1つずつ消去し、効率よくセットビット数をカウントしています。

このプログラムをコンパイルして実行すると、次のような出力が得られます。

出力結果

Minimum number = 3