XOR 연산으로 이진 문자열의 2의 보수 구하기

이 글에서는 XOR 연산을 활용해 주어진 이진 문자열의 2의 보수(2's Complement)를 구하는 방법을 알아봅니다.

2의 보수의 기본 개념

2의 보수는 컴퓨터에서 음의 정수를 표현할 때 가장 널리 쓰이는 방식입니다. 수학적으로는 1의 보수(모든 비트를 반전한 값)에 1을 더한 값과 같습니다. 여기서는 별도의 덧셈 단계 없이, 문자열을 한 번만 순회하면서 XOR 연산만으로 2의 보수를 바로 계산하는 기법을 다룹니다.

접근 방법

문자열을 최하위 비트(LSb, 가장 오른쪽 비트)부터 왼쪽 방향으로 순회하며 다음 규칙을 적용합니다.

• 처음으로 1이 등장하기 전까지의 모든 0은 그대로 둡니다.
• 처음 만나는 1 역시 그대로 유지합니다.
• 그 이후 왼쪽에 있는 모든 비트는 XOR 연산으로 반전시킵니다.
• 문자열에 1이 하나도 없다면, 맨 앞에 '1'을 붙여 결과로 반환합니다.

알고리즘

get2sComp(bin)

begin
    len := 이진 문자열의 길이
    flag := false
    i를 len-1부터 0까지 감소시키며 반복:
        if bin[i]가 '0'이고 flag가 설정되지 않았으면
            건너뛰고 다음 반복으로 진행
        else
            if flag가 설정되어 있으면
                bin[i] := bin[i]의 반전 값
            end if
            flag := true
        end if
    반복 종료
    if flag가 끝까지 설정되지 않았으면
        bin 앞에 '1'을 붙여 반환
    else
        return bin
    end if
end

C++ 구현 예제

#include <iostream>
using namespace std;

string get2sComplement(string bin) {
    int n = bin.length();
    bool flag = false; // 1을 발견했는지 나타내는 플래그
    for (int i = n - 1; i >= 0; i--) { // 마지막 비트부터 순회
        if (bin[i] == '0' && !flag) {
            continue;
        } else {
            if (flag)
                bin[i] = ((bin[i] - '0') ^ 1) + '0'; // XOR로 비트를 반전한 뒤 ASCII 문자로 변환
            flag = true;
        }
    }
    if (!flag) // 1이 하나도 없으면 앞에 '1'을 붙여 반환
        return "1" + bin;
    else
        return bin;
}

int main() {
    string str;
    cout << "Enter a binary string: ";
    cin >> str;
    cout << "2's complement of " << str << " is " << get2sComplement(str);
}

실행 결과

Enter a binary string: 10110110
2's complement of 10110110 is 01001010

동작 과정 살펴보기

입력이 10110110일 때의 처리 과정은 다음과 같습니다.

1. 오른쪽 끝부터 탐색을 시작합니다. 첫 번째 비트 '0'은 아직 1을 만나기 전이므로 그대로 둡니다.
2. 다음 비트 '1'을 처음 만나면 값을 유지하고 플래그(flag)를 설정합니다.
3. 플래그가 설정된 이후에는 왼쪽의 나머지 비트를 모두 반전합니다.

그 결과 10110110은 01001010으로 변환되며, 이것이 바로 입력값의 2의 보수입니다.

복잡도 분석

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이고, 추가 배열 없이 제자리(in-place)에서 처리되므로 공간 복잡도는 O(1)입니다.