C++로 숫자의 K번째 최하위 비트(LSB) 구하는 방법

이 문제에서는 두 개의 숫자 n과 k가 주어지며, 우리의 과제는 숫자 n의 k번째 최하위 비트(Least Significant Bit)를 출력하는 것입니다.

예시를 통해 문제를 이해해 보겠습니다.

입력: n = 12, k = 3
출력: 1
설명:
n의 이진수 표현을 살펴보면 다음과 같습니다. 12 = 1100

위 예제에서 3번째 최하위 비트의 값은 1입니다.

문제 해결 접근 방법

이 문제를 해결하기 위해서는 숫자의 이진 비트를 활용하여 k번째 비트를 추출해야 합니다. 이를 위해 비트 시프트(bit shift) 연산을 사용합니다.

구체적인 방법은 다음과 같습니다.

• 숫자 1을 왼쪽으로 (k-1)번 시프트하여 k번째 자리만 1인 마스크(mask)를 만듭니다.
• 원래 숫자와 마스크를 비트 AND(&) 연산합니다.
• 연산 결과가 0이 아니라면 해당 비트는 1이고, 0이라면 해당 비트는 0입니다.

예를 들어, k = 3일 때 (1 << 2)는 이진수 100이 되고, 이 값과 n을 AND 연산하면 n의 3번째 비트 값만 남게 됩니다.

구현 예제

아래 코드는 위에서 설명한 솔루션의 구현을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N = 12, K = 3;
    cout<<K<<"th significant bit of "<<N<<" is : ";
    bool kthLSB = (N & (1 << (K-1)));
    cout<<kthLSB;
    return 0;
}

출력 결과

3th significant bit of 12 is : 1

이처럼 비트 연산자를 활용하면 별도의 반복문 없이 O(1)의 시간 복잡도로 특정 위치의 비트 값을 빠르고 효율적으로 확인할 수 있습니다.