C++에서 숫자의 비트를 효율적으로 반전시키는 방법

개요

이 튜토리얼에서는 숫자의 비트를 효율적으로 반전시키는 C++ 프로그램을 살펴봅니다.

음이 아닌 정수가 하나 주어졌을 때, 해당 숫자를 이진수 형태로 변환한 뒤 모든 비트를 반전시키고, 최종적으로 반전된 값의 10진수 등가 값을 출력하는 것이 목표입니다.

예제 설명

입력값이 17이라면, 17은 이진수로 10001입니다. 각 비트를 반전하면 01110이 되고, 이를 10진수로 변환하면 14가 됩니다.

구현 코드

#include <bits/stdc++.h>
using namespace std;

// 숫자의 비트를 반전하는 함수
int invert_bit(int n){
   int x = log2(n);
   int m = 1 << x;
   m = m | m - 1;
   n = n ^ m;
   return n;
}

int main(){
   int n = 17;
   cout << invert_bit(n) << endl;
   return 0;
}

출력 결과

14

코드 동작 원리

이 알고리즘은 다음 세 단계로 동작합니다.

1. log2(n)을 통해 주어진 숫자의 최상위 비트(MSB) 위치를 구합니다.
2. 1 << x로 최상위 비트만 1인 마스크를 만든 뒤, m | (m - 1) 연산을 통해 최상위 비트부터 최하위 비트까지 모두 1로 채워진 마스크를 완성합니다.
3. 원래 숫자에 이 마스크를 XOR(^) 연산하면 유효 비트 범위 내의 모든 비트가 한 번에 반전됩니다.

이 방식은 숫자를 이진수 문자열로 변환하지 않고도 비트 연산만으로 처리하기 때문에 매우 효율적이며, 불필요한 선행 비트까지 함께 뒤집어 잘못된 값이 나오는 문제를 마스크 생성 과정에서 자연스럽게 방지할 수 있습니다.