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의 거듭제곱을 모두 더하면 이것이 답이 됩니다.

Example

#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";
}

Output

14

이 방법에서는 범위를 반복하고 범위에 있는 숫자 중 2개의 거듭제곱을 더합니다. 이 프로그램의 시간 복잡도는 O(N)이며, 여기서 N은 범위의 크기입니다. 그러나 주어진 문제에 비트 지식을 적용함으로써 시간 복잡도를 더욱 향상시킬 수 있습니다.

효율적인 방법

이 방법에서는 간단히 답을 계산하는 공식을 구성합니다.

Example

#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";
}

Output

14

이 방법에서는 답을 계산하는 공식을 공식화합니다.

위 코드에 대한 설명

아시다시피 주어진 범위에서 설정된 비트를 사용하여 숫자를 계산해야 하므로 이 방법에서는 모든 비트가 설정된 0에서 R까지의 숫자를 찾습니다. 그런 다음 모든 비트가 1에서 (L-1)로 설정된 숫자를 빼야 하므로 이 관찰을 공식화합니다. 주어진 코드의 전체 시간 복잡도는 O(1)입니다. 즉, 일정한 시간 복잡도입니다. 이는 일정한 시간에 어떤 답이라도 계산할 수 있음을 의미합니다.

결론

이 글에서는 "L번째와 R번째 인덱스 사이에 비트가 설정된 숫자만" 프로그램을 작성하겠습니다. 우리는 또한 이 문제를 해결하기 위해 C++ 프로그램과 완전한 방법(일반적이고 효율적인)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 L번째와 R번째 인덱스 사이에 설정된 비트만 있는 숫자 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!