C++에서 정수의 이진 표현에서 k번째 비트 값 구하기

이 문제에서는 두 개의 값 n과 k가 주어지며, 우리의 과제는 주어진 수의 이진 표현에서 k번째 비트의 값을 구하는 것입니다.

문제 이해를 위한 예시

먼저 예시를 통해 문제를 살펴보겠습니다.

입력 : n = 5, k = 2
출력 : 0

해설 −

5의 이진수 = 0101
두 번째 LSB(최하위 유효 비트)는 0입니다.

해결 접근 방법

이 문제는 비트 연산(bitwise operation)을 활용하면 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 마스크 생성 : (1 << (k - 1))을 사용하면 k번째 자리에만 1이 설정되고 나머지 비트는 모두 0인 숫자를 만들 수 있습니다.
2. AND 연산 : 원래 수 n과 위 마스크를 비트 단위 AND(&) 연산하면 k번째 비트만 남고 나머지 비트는 모두 0이 됩니다.
3. 오른쪽 시프트 : 연산 결과를 (k - 1)비트만큼 오른쪽으로 시프트하면 해당 비트가 최하위 자리로 이동하여 최종적으로 0 또는 1의 값을 얻게 됩니다.

예제 코드

아래 프로그램은 위 해결 방법의 실제 동작을 보여줍니다.

#include <iostream>
using namespace std;
void findKBitVal(int n, int k){
   cout<< ((n & (1 << (k - 1))) >> (k - 1));
}
int main(){
   int n = 29, k = 4;
   cout<<"이 수의 이진 표현에서 k번째 비트의 값은 ";
      findKBitVal(n, k);
      return 0;
}

출력

이 수의 이진 표현에서 k번째 비트의 값은 1

위 코드에서 n = 29의 이진 표현은 11101이며, 4번째 비트(왼쪽에서 세 번째)가 1이므로 출력값은 1이 됩니다. 이 방식은 추가적인 문자열 변환 없이 O(1) 시간 복잡도로 특정 비트의 값을 즉시 확인할 수 있는 효율적인 기법입니다.