C++에서 숫자의 최상위 세트 비트(MSB) 값 찾는 방법

개요

이 글에서는 주어진 숫자에서 최상위 세트 비트(Most Significant Bit, MSB)의 값을 찾는 방법을 알아봅니다. MSB의 값은 항상 2의 거듭제곱 형태라는 점이 핵심입니다.

예를 들어 숫자가 10이라면 이진수로 1010으로 표현되며, 가장 높은 자리에 있는 세트 비트의 값은 8(2³)입니다. 즉, 먼저 MSB의 위치 k를 구한 후, k번째 비트가 세트된 값인 2^k를 계산하면 원하는 결과를 얻을 수 있습니다.

동작 원리

1. log2(n) 함수를 사용하여 MSB의 위치 k를 구합니다.
2. pow(2, k)를 사용하여 k번째 위치의 비트 값(2^k)을 계산합니다.
3. 정수형으로 변환하여 반환합니다.

C++ 코드 예제

#include<iostream>
#include<cmath>
using namespace std;

int msbBitValue(int n) {
    int k = (int)(log2(n));
    return (int)(pow(2, k));
}

int main() {
    int n = 150;
    cout << "MSB bit value is: " << msbBitValue(n);
}

출력 결과

MSB bit value is: 128

코드 설명

숫자 150을 이진수로 표현하면 10010110입니다. 여기서 가장 왼쪽의 세트 비트는 7번째 위치에 있으므로, MSB 값은 2⁷인 128이 됩니다.

log2(n)의 정수 부분은 곧 MSB의 위치를 의미합니다. 예를 들어 log2(150) ≈ 7.23이므로 정수 부분인 7이 MSB의 위치가 되고, 이를 바탕으로 128을 계산할 수 있습니다.

이 방식은 시간 복잡도 O(log n)으로 매우 간단하게 MSB 값을 구할 수 있으며, 비트 연산 기반의 다른 방법들과 함께 자주 활용됩니다.