C++を使用して、L番目とR番目のインデックスの間に設定されたビットのみを持つ数値を見つけます

指定された問題では、指定された範囲 L、R の間に設定されたビットがすべて含まれる数値の値を見つける必要があります。例: −

Input: L = 1, R = 5
Output: 62
Explanation: representation of given L and R in binary form is 0..0111110

Input: L = 1, R = 4
Output: 30
Explanation: representation of given L and R in binary form is 0..11110

解決策を見つける方法

与えられた問題において、力任せの方法と効率的な方法の 2 つの方法について説明します。

ブルートフォース法

この方法では、指定された範囲を反復処理し、指定された範囲内のすべての 2 の累乗を合計するだけで、これが答えになります。

例

#include<bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // the given range
   int ans = 0; // our answer
   for(int i = L; i <= R; i++) // traversing through the whole range
      ans += pow(2, i); // adding values to the answer.
   cout << ans << "\n";
}

出力

14

このアプローチでは、範囲を反復処理し、範囲内の数値の 2 の累乗を単純に加算します。このプログラムの時間計算量は O(N) です。ここで、N は範囲のサイズです。しかし、与えられた問題にビット知識を適用することで、時間計算量をさらに改善できます。

効率的な方法

この方法では、答えを計算するための式を単純に構築します。

例

#include<bits/stdc++.h>
using namespace std;
int main() {
   int L = 1, R = 3; // the given range
   int ans = 0; // our answer
   for(int i = L; i <= R; i++) // traversing through the whole range
      ans += pow(2, i); // adding values to the answer.
   cout << ans << "\n";
}

出力

14

このメソッドでは、答えを計算するための式を定式化します。

上記のコードの説明

ご存知のとおり、指定された範囲内でビットを設定して数値を数える必要があるため、このメソッドではビットが数値に設定されていることがわかります。次に、すべてのビットが 1 から (L-1) に設定された数値を減算する必要があるため、この観察を定式化します。指定されたコードの全体的な時間計算量は O(1) であり、これは定数時間計算量であり、定数時間で任意の答えを計算できることを意味します。

結論

この記事では「L番目とR番目のインデックスの間にビットが設定されている数値のみ」を対象としたプログラムを書きます。また、C プログラムと、この問題を解決するための完全な方法 (一般的かつ効率的) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++を使用して、L番目とR番目のインデックスの間に設定されたビットのみを持つ数値を見つけますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。