C++로 L번째와 R번째 인덱스 사이에만 비트가 설정된 숫자 구하기

이 문제에서는 주어진 범위 L과 R 사이에 있는 모든 비트가 설정(set)된 숫자의 값을 구해야 합니다. 즉, L번째 비트부터 R번째 비트까지만 1이고 나머지 비트는 모두 0인 숫자를 찾는 것입니다. 예를 들어 다음과 같습니다.

입력: L = 1, R = 5
출력: 62
설명: 주어진 L과 R을 이진수로 표현하면 0..0111110 입니다.

입력: L = 1, R = 4
출력: 30
설명: 주어진 L과 R을 이진수로 표현하면 0..011110 입니다.

해결 방법

이 문제는 크게 두 가지 접근법으로 해결할 수 있습니다. 하나는 단순 반복문을 사용하는 브루트 포스(Brute Force) 방식이고, 다른 하나는 비트 연산 수식을 활용한 효율적인(Efficient) 방식입니다.

브루트 포스 접근법

이 방식은 매우 직관적입니다. 주어진 범위 [L, R]을 처음부터 끝까지 순회하면서 각 위치에 해당하는 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

이 코드는 범위 내의 모든 위치에 대해 2의 거듭제곱을 계산하여 더하는 단순한 방식입니다. 시간 복잡도는 O(N)(N은 범위의 크기)입니다. 하지만 비트 연산에 대한 지식을 활용하면 시간 복잡도를 훨씬 더 개선할 수 있습니다.

효율적인 접근법

이 방식에서는 반복문 없이 답을 한 번에 계산할 수 있는 수식을 만들어 사용합니다. 먼저 0번째 비트부터 R번째 비트까지 모두 1로 설정된 숫자를 만든 다음, 여기서 0번째 비트부터 (L-1)번째 비트까지 모두 1로 설정된 숫자를 빼주면, 정확히 L번째부터 R번째까지만 비트가 설정된 숫자를 얻을 수 있습니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int main() {
    int L = 1, R = 3; // 주어진 범위
    // 0~R번 비트가 모두 1인 값에서 0~(L-1)번 비트가 1인 값을 제외
    int ans = ((1 << (R + 1)) - 1) - ((1 << L) - 1);
    cout << ans << "\n";
}

출력 결과

14

코드 설명

((1 << (R + 1)) - 1)은 0번째 비트부터 R번째 비트까지 모두 1인 숫자를 의미합니다. 여기서 ((1 << L) - 1), 즉 0번째 비트부터 (L-1)번째 비트까지 모두 1인 숫자를 빼면 남는 것은 정확히 L번째부터 R번째까지만 설정된 비트입니다. 이러한 관찰을 바탕으로 위와 같은 수식을 세울 수 있습니다. 이 코드의 전체 시간 복잡도는 O(1)로, 상수 시간 안에 어떤 범위의 답이든 즉시 계산할 수 있다는 것이 가장 큰 장점입니다.

결론

이 글에서는 "L번째 인덱스와 R번째 인덱스 사이에만 비트가 설정된 숫자"를 구하는 문제를 다루었습니다. 단순 반복문을 사용하는 브루트 포스 방식(O(N))과 비트 연산 수식을 활용한 효율적인 방식(O(1)), 두 가지 접근법을 C++ 코드와 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 글이 여러분에게 도움이 되기를 바랍니다.