C++로 다음 숫자의 이진 표현 구하기

문제 개요

이 문제에서는 하나의 숫자가 이진수 형태로 주어지며, 해당 숫자에 1을 더한 값, 즉 다음 숫자의 이진 표현을 구해야 합니다.

이진 표현(binary representation)이란 숫자의 밑(base)을 2로 변환하여 0과 1만으로 나타내는 방식입니다. 예를 들어, 십진수 14의 이진 표현은 1110입니다.

따라서 이진수 형태의 숫자 n이 주어졌을 때, n+1의 이진 표현을 구하는 것이 이 글의 목표입니다.

이진수 덧셈의 기본 원리

이 문제를 해결하려면 먼저 이진수 덧셈의 기본 규칙을 이해해야 합니다. 이진수에서 0 또는 1에 1을 더하면 결과는 다음과 같습니다.

0 + 1 = 1
1 + 1 = 10 (자리올림 발생)

예시

실제 예시를 통해 문제 해결 과정을 살펴보겠습니다.

입력: 010010111
출력: 010011000
설명: (010010111)₂는 십진수 152에 해당하며, 다음 숫자인 153의 이진 표현은 (010011000)₂입니다.
여기서는 숫자의 이진 표현에 이진수 1을 더하는 이진 덧셈 방식을 활용합니다.

위 예시에서 알 수 있는 핵심 규칙은 다음과 같습니다. 이진수 1을 더하면 오른쪽 끝부터 연속된 모든 1이 0으로 바뀌고, 처음 만나는 0이 1로 뒤집힙니다. 이 논리를 바탕으로 알고리즘을 설계해 보겠습니다.

알고리즘

오른쪽에서 왼쪽으로 탐색을 시작합니다. (인덱스 n-1부터 0까지)
0을 만나면 1로 바꾸고 반복을 종료합니다.
1을 만나면 0으로 바꾸고 계속 진행합니다.
모든 비트가 1이어서 0을 만나지 못한 경우, 문자열 맨 앞에 1을 추가합니다. (예: "111" → "1000")
최종 결과 문자열을 출력합니다.

C++ 코드 구현

이제 위 알고리즘을 C++ 코드로 구현해 보겠습니다.

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

string nextBinary(string num) {
    int l = num.size();
    int flag = 0;
    for (int i = l - 1; i >= 0; i--) {
        if (num.at(i) == '0') {
            num.at(i) = '1';   // 처음 만난 0을 1로 뒤집음
            flag = 1;
            break;
        } else {
            num.at(i) = '0';   // 연속된 1을 0으로 변경
        }
    }
    // 모든 비트가 1이었던 경우 처리 (예: "111" → "1000")
    if (flag == 0)
        num = "1" + num;
    return num;
}

int main() {
    string number = "0111010111";
    cout << "입력 수의 이진 표현: " << number << endl;
    cout << "다음 수의 이진 표현: " << nextBinary(number);
    return 0;
}

실행 결과

입력 수의 이진 표현: 0111010111
다음 수의 이진 표현: 0111011000

동작 설명 및 복잡도 분석

입력 "0111010111"의 경우, 오른쪽 끝부터 살펴보면 마지막 두 비트가 모두 1이므로 0으로 바뀌고, 그 앞에 있던 0이 1로 뒤집혀 최종적으로 "0111011000"이 됩니다.

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)(n은 비트 길이)입니다. 일반적인 경우 입력 문자열 자체를 수정하므로 추가 공간은 O(1)이며, 모든 비트가 1인 특수한 경우에만 새 문자열을 생성하므로 이때만 O(n)의 공간이 필요합니다.