使用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的冪相加，這將是我們的答案。

範例

#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

在這個方法中，我們制定了一個計算答案的公式。

上述程式碼的解釋

如您所知，我們需要計算給定範圍內具有設定位的數字，因此在這種方法中，我們找到一個從0到R的所有位都設定的數字。然後我們需要從1到（L-1）中減去一個所有位元都設定的數字，因此我們制定了這個觀察結果。給定程式碼的總體時間複雜度為O(1)，即常數時間複雜度，這意味著我們可以在常數時間內計算任何答案。

結論

本文將為「僅在L-th和R-th索引之間具有設定位的數字」編寫一個程式。我們也學習了解決此問題的C 程序和完整的方法（普通和高效）。我們可以使用其他語言（如C、Java、Python和其他語言）編寫相同的程式。希望您會發現本文有幫助。

以上是使用C++找出在第L個與第R個索引之間只有設定位的數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！