C++에서 정수의 1의 보수(1's Complement) 구하는 방법

개요

이 글에서는 정수의 1의 보수(1's Complement)를 구하는 방법을 알아보겠습니다. C++에서는 비트 반전 연산자(~)를 사용하면 이 작업을 매우 빠르게 수행할 수 있지만, 이 연산자는 32비트 전체(4바이트 정수)에 대한 보수를 만들어냅니다. 여기서 우리가 원하는 것은 해당 숫자가 실제로 사용하는 n비트에 대한 보수입니다.

예를 들어 22라는 숫자가 있다고 가정해 보겠습니다. 22의 이진수 표현은 10110이며, 이를 비트 단위로 반전하면 01001, 즉 10진수로 9가 됩니다. 그렇다면 이 값을 어떻게 계산할 수 있을까요?

알고리즘 설명

먼저 주어진 숫자의 비트 수를 구해야 합니다. 이 값을 c라고 하겠습니다(22의 경우 c = 5). 다음으로 c개의 1, 즉 11111을 만들어야 합니다.

이는 1을 왼쪽으로 c번 시프트한 뒤 1을 빼면 간단히 구할 수 있습니다. 1을 왼쪽으로 5번 시프트하면 100000이 되고, 여기서 1을 빼면 11111이 됩니다. 마지막으로 이 마스크 값과 원래 숫자(10110)를 XOR 연산하면 원하는 n비트 보수를 얻을 수 있습니다.

예제 코드

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

int findComplement(int n) {
    int bit_count = floor(log2(n)) + 1;   // 숫자의 실제 비트 수 계산
    int ones = ((1 << bit_count) - 1);    // c개의 1로 이루어진 마스크 생성
    return ones ^ n;                       // XOR로 비트 반전
}

int main() {
    int number = 22;
    cout << "One's Complement of " << number << " is: " << findComplement(number);
}

실행 결과

One's Complement of 22 is: 9

코드 설명

findComplement 함수의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

1단계: floor(log2(n)) + 1을 사용해 숫자 n을 표현하는 데 필요한 비트 수를 구합니다. 22의 경우 log2(22)는 약 4.46이므로, floor를 적용하면 4가 되고 여기에 1을 더해 5비트임을 알 수 있습니다.

2단계: (1 << bit_count) - 1을 통해 5개의 1로 이루어진 마스크 11111(10진수 31)을 만듭니다.

3단계: 마스크와 원래 숫자를 XOR 연산합니다. XOR은 같은 비트끼리는 0, 다른 비트끼리는 1을 반환하므로, 1과 0이 뒤바뀐 보수 값이 자연스럽게 계산됩니다. 즉, 11111 XOR 10110 = 01001이 되어 결과값 9를 얻게 됩니다.

이 방식은 32비트 전체를 반전하는 기본 연산자(~)와 달리, 숫자의 유효 비트만 정확히 반전하므로 불필요한 선행 1이 생기지 않는다는 장점이 있습니다.