C++でビットを再配置して最大の数を作る方法

問題文

符号なし整数が与えられたとき、その数が持つビットを並べ替えて作ることができる最大の数を求めます。

たとえば、入力が 8 の場合、その2進数表現は次のようになります。

00000000000000000000000000001000

この数を最大化するには、最上位ビット(MSB)を1にします。すると数は 2147483648 となり、その2進数表現は次のとおりです。

10000000000000000000000000000000

アルゴリズム

1. 与えられた数の2進数表現におけるセットビット(1になっているビット)の個数 n を数える
2. 下位 n ビットがすべて1になる数を作る
3. その数を (32 − n) ビットだけ左にシフトする

この手順により、1になっているビットがすべて最上位側に集められ、32ビットで表現できる最大の数が得られます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
unsigned getMaxNumber(unsigned num){
    int n = __builtin_popcount(num);
    if (n == 32) {
        return num;
    }
    unsigned result = (1 << n) - 1;
    return (result << (32 - n));
}
int main(){
    unsigned n = 8;
    cout << "Maximum number = " << getMaxNumber(n) << endl;
    return 0;
}

コードのポイント

• __builtin_popcount(num):GCCやClangで利用できる組み込み関数で、引数の整数に含まれる1のビット数を返します。
• (1 << n) - 1:下位 n ビットがすべて1の数(例:n=4なら 1111)を生成します。
• すべての32ビットがすでに1の場合(n=32)は、これ以上大きくできないため元の値をそのまま返します。

出力

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

Maximum number = 2147483648