C++로 구하는 설정된 비트 하나를 변경한 n 미만의 최대 정수

이 문제에서는 하나의 정수 n이 주어집니다. 우리가 해야 할 일은 숫자의 이진 표현에서 설정된(set) 비트 단 하나를 변경하여 만들 수 있는 수 중에서 n보다 작은 가장 큰 수를 출력하는 것입니다.

문제 이해하기

예시를 통해 문제를 자세히 살펴보겠습니다.

입력: n = 3
출력: 2
설명: (3)₁₀ = (011)₂
설정된 비트 하나를 뒤집으면 001과 010을 얻을 수 있으며, 이 중 더 큰 값은 010, 즉 2입니다.

해결 접근 방법

이 문제를 해결하는 핵심은 가장 오른쪽에 있는 설정된 비트(최하위 설정 비트)를 찾아 0으로 바꾸는 것입니다. 해당 비트를 0으로 만들면 비트 하나만 변경해서 얻을 수 있는 수 중 n보다 작으면서 가장 큰 값을 구할 수 있습니다.

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

먼저 n & -n 연산을 사용하면 n의 최하위 설정 비트 값만 남길 수 있습니다. 여기에 log₂를 적용하고 1을 더하면 해당 비트의 위치(오른쪽에서 몇 번째인지)를 알아낼 수 있습니다. 이후 NOT(~) 연산과 왼쪽 시프트를 조합해 그 위치의 비트만 0으로 만들면 원하는 결과를 얻을 수 있습니다.

예제 코드

위 접근 방식을 구현한 C++ 프로그램은 다음과 같습니다.

#include<iostream>
#include<math.h>
using namespace std;
int returnRightSetBit(int n) {
    return log2(n & -n) + 1;
}
void previousSmallerInteger(int n) {
    int rightBit = returnRightSetBit(n);
    cout<<(n&~(1<<(rightBit - 1)));
}
int main() {
    int n = 3452;
    cout<<"The number is "<<n<<"\nThe greatest integer smaller than the number is : ";
    previousSmallerInteger(n);
    return 0;
}

실행 결과

The number is 3452
The greatest integer smaller than the number is : 3448

예제에서 입력값 3452의 이진 표현에서 최하위 설정 비트를 0으로 바꾸자 3448이 출력되었습니다. 이는 비트 하나만 변경하여 만들 수 있는 수 중 3452보다 작은 가장 큰 정수입니다.