C++で両端のビットを入れ替えて符号なし整数を最大化する方法

問題概要

与えられた符号なし整数を、両端に位置するビット同士を入れ替えることによって最大化します。具体的には、最下位ビットと最上位ビット、下から2番目と上から2番目といった具合に、対称な位置にあるビットを順に交換していきます。

例として、入力が 8 の場合を考えてみましょう。2進数表現は次のようになります。

00000000 00000000 00000000 00001000

対称な位置のビットを入れ替えると、セットされているビット（第3ビット）は第28ビットへ移動し、結果は次のようになります。

00010000 00000000 00000000 00000000

この数値の10進数での値は 268435456 です。

アルゴリズム

1. 元の数値のコピーを作成します。
2. 下位側のビットが1で、対応する上位側のビットが0である場合、その2ビットだけを入れ替えます。下位側のビット位置が上位側のビット位置より小さい間、この処理を繰り返します。
3. 新しい数値を返します。

C++による実装例

#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
ull getMaxNumber(ull num){
    ull origNum = num;
    int bitCnt = sizeof(ull) * 8 - 1;
    int cnt = 0;
    for(cnt = 0; cnt < bitCnt; ++cnt, --bitCnt) {
        int m = (origNum >> cnt) & 1;
        int n = (origNum >> bitCnt) & 1;
        if (m > n) {
            int x = (1 << cnt | 1 << bitCnt);
            num = num ^ x;
        }
    }
    return num;
}
int main(){
    ull num = 8;
    cout << "Maximum number = " << getMaxNumber(num) << endl;
    return 0;
}

コードの解説

• sizeof(ull) * 8 - 1 により、unsigned long long 型の最上位ビット位置（63）を求めています。
• cnt は下位側からのビット位置、bitCnt は上位側からのビット位置を表し、ループが進むごとに両者は中央へ向かって近づいていきます。
• (origNum >> cnt) & 1 で下位側のビット値を、(origNum >> bitCnt) & 1 で上位側のビット値をそれぞれ取得します。
• 下位側が1・上位側が0の場合（m > n）のみ、XOR演算によって2つのビットを効率よく入れ替えます。これにより、セットされているビットがより高い桁へ移動し、数値全体が大きくなります。

出力

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

Maximum number = 268435456