C++でビット単位のAND演算を使って0からXへの変換に必要な最大ステップ数を求める方法

問題の概要

この問題では、整数 X が与えられ、0 から X への変換にかかる最大ステップ数を求めます。

有効な変換とは

ある値 A から別の値 B への変換が 1 ステップとしてカウントされるのは、次の条件を満たす場合です。

• A != B（A と B は異なる値であること）
• A & B = A（& はビット単位の AND 演算）

つまり、A から B への変換が 1 ステップであり、0 から X への変換における最大ステップ数を計算するプログラムを作成します。

入出力例

入力： X = 7

出力： 3

解説

0 から 7 への変換は、以下の手順で行われます。

Step1: 0(00) → 1(01)：0 != 1 かつ 0&1 = 0 なので、00 => 01 に変換可能
Step2: 1(001) → 3(011)：1 != 3 かつ 1&3 = 1 なので、001 => 011 に変換可能
Step3: 3(0011) → 7(0111)：3 != 7 かつ 3&7 = 3 なので、0011 => 0111 に変換可能

解法のアプローチ

この問題を解く鍵となるのは、X のセットビット（値が 1 になっているビット）の個数を数えることです。その個数が、0 から X への最大変換回数となります。

最大の変換回数を得るためには、セットビットごとに 1 ビットずつ順番に立てていく必要があります。1 ビットずつ段階的に変換を行うことで、ステップ数が最大化されます。

A から B への変換では、A のすべてのセットビットが B にもセットされている必要がありますが、その逆は必須ではありません。したがって、最小の変換回数は 1 です。0 にはセットビットが存在しないため、最初の変換は直接行うことができるのです。

上記の例で示したように、各数値のバイナリ表現とビット単位 AND の結果を比較すると、この性質がよく分かります。

C++での実装例

以下は、この解法を実装したプログラムです。計算量は O(log X) であり、非常に効率的です。

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

// セットビットの数をカウントして最大ステップ数を返す関数
int maxtransformation(int x){
    int steps = 0;
    while (x) {
        steps += x & 1;   // 最下位ビットが 1 ならカウント
        x >>= 1;          // 右シフトして次のビットへ
    }
    return steps;
}

int main(){
    int x = 7;
    cout<<"The maximum number of steps to transform 0 to "<<x<<" with bitwise AND are "<<maxtransformation(x);
    return 0;
}

出力結果

The maximum number of steps to transform 0 to 7 with bitwise AND are 3

まとめ

0 から X への変換における最大ステップ数は、X を二進数で表したときのセットビットの個数と一致します。ビットごとに段階的に値を大きくしていくことで、すべての変換条件（A != B かつ A & B = A）を満たしながら最大のステップ数を達成できます。