C++でL番目からR番目のインデックス間のみビットがセットされた数を求める方法

問題の概要

この問題では、指定された範囲LからRの間にあるすべてのビットがセット（1）になっている数の値を求めます。具体的な例を見てみましょう。

入力: L = 1, R = 5
出力: 62
説明: LとRを2進数で表すと 0..0111110 となります

入力: L = 1, R = 4
出力: 30
説明: LとRを2進数で表すと 0..11110 となります

解法へのアプローチ

この問題に対して、シンプルな全探索（ブルートフォース）と、ビット演算を活用した効率的なアプローチの2つの方法を紹介します。

方法1: 全探索（ブルートフォース）

このアプローチでは、指定された範囲を順番に走査し、範囲内の各位置に対応する2のべき乗をすべて加算します。その合計が答えになります。

#include <bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // 指定された範囲
   int ans = 0; // 答えを格納する変数
   for(int i = L; i <= R; i++) // 範囲全体を走査
      ans += pow(2, i); // 各位置の2のべき乗を加算
   cout << ans << "\n";
}

出力

14

このアプローチでは、範囲内を1つずつ確認しながら該当する2のべき乗を加算していきます。このプログラムの時間計算量はO(N)です（Nは範囲のサイズ）。しかし、ビット演算に関する知識を応用することで、計算量をさらに改善できます。

方法2: 効率的なアプローチ（O(1)）

このアプローチでは、答えを直接計算できる数式を導き出します。考え方は以下の通りです。

• 0からRまでのすべてのビットが1になっている数：(2^R+1) − 1
• 0からL−1までのすべてのビットが1になっている数：(2^L) − 1
• 前者から後者を引けば、LからRの間だけビットがセットされた数が得られます

#include <bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // 指定された範囲
   // 0〜Rまですべてのビットが立った数から、0〜(L-1)まですべてのビットが立った数を引く
   long long ans = ((1LL << (R + 1)) - 1) - ((1LL << L) - 1);
   cout << ans << "\n";
}

出力

14

コードの解説

上記のコードでは、まず0からRまでのすべてのビットがセットされた数を生成し、そこから0からL−1までのすべてのビットがセットされた数を減算しています。これにより、指定範囲L〜Rの間のみビットが立った数が一瞬で求まります。ループ処理が不要になるため、このコード全体の時間計算量はO(1)、つまり定数時間となります。これは、範囲がどれほど大きくても一定の時間で答えを計算できることを意味します。

まとめ

この記事では、「L番目とR番目のインデックスの間でのみビットがセットされた数」を求めるプログラムについて解説しました。全探索によるO(N)のアプローチと、ビット演算を活用したO(1)の効率的なアプローチの両方を、C++のコード例とともに学びました。同様のロジックはC、Java、Pythonなど他の言語でも実装可能です。この記事が皆さまのお役に立てば幸いです。