C++で1つのセットビットを変更して得られる、nより小さい最大の整数

問題の概要

この問題では、整数 n が与えられます。求められているのは、n の2進数表現における「セットビット（1になっているビット）」を1つだけ変更することで作れる数のうち、n より小さい最大の整数を出力することです。

具体例を見てみましょう。

入力: n = 3
出力: 2
解説: (3)10 = (011)2
セットビットを1つ反転すると、001 と 010 が得られます。このうち大きいのは 010、すなわち 2 です。

解き方のアプローチ

この問題を解く鍵は、「最も右側にあるセットビット」に注目することです。n より小さくなるようにビットを1つだけ変更するなら、最下位のセットビットを0に反転するのが最適です。これにより、1ビットの変更で実現できる n 未満の最大の整数が得られます。

直感的に考えると、より上位のビットを0にすると数値は大きく減少してしまいますが、最下位のセットビットを0にすれば減少量は最小限に抑えられます。

C++による実装例

以下は、この解法を実装したC++プログラムです。

#include<iostream>
#include<math.h>
using namespace std;
int returnRightSetBit(int n) {
   return log2(n & -n) + 1;
}
void previousSmallerInteger(int n) {
   int rightBit = returnRightSetBit(n);
   cout<<(n&~(1<<(rightBit - 1)));
}
int main() {
   int n = 3452;
   cout<<"The number is "<<n<<"\nThe greatest integer smaller than the number is : ";
   previousSmallerInteger(n);
   return 0;
}

実行結果

The number is 3452
The greatest integer smaller than the number is : 3448

コードの解説

• n & -n: 2の補数表現を利用したテクニックで、n の最下位のセットビットだけを取り出します。
• log2(...) + 1: 取り出したビットの位置（右から何番目か）を求めます。
• n & ~(1 << (rightBit - 1)): 該当する位置のビットだけを0にクリアし、目的の整数を生成します。

この例では n = 3452 の場合、出力は 3448 となり、確かに1ビットの変更で得られる n 未満の最大整数になっています。