이 문제에서는 숫자의 이진 표현이 주어지고 다음 숫자의 이진 표현, 즉 주어진 숫자에 1을 더한 결과를 찾아야 합니다.
이진 표현 의 수는 수의 밑수를 2로 변경하고 0 또는 1만 사용하여 숫자를 나타내는 것입니다.
예를 들어, 14의 이진 표현은 1110입니다.
따라서 여기에 숫자가 주어집니다. n을 이진 형식으로 가정해 보겠습니다. 그리고 우리는 n+1의 이진 표현을 찾아야 합니다.
이 문제를 해결하려면 이진 덧셈의 기본 사항을 알아야 합니다. 이진법으로 0 또는 1에 1을 더하면 어떻게 되는지 알아봅시다.
0 + 1 =1
1 + 1 =10
예시
위의 문제를 해결하는 방법에 대한 예를 살펴보겠습니다.
Input: 010010111 Output: 010011000 Explanation : (010010111)2 is the binary representation of 152 and the next number will be 153 whose binary representation is (010011000)2. We will use binary addition here and add binary (1)2 to the binary representation of the number.
위의 예에서 숫자에 이진수 1을 추가하면 오른쪽에서 시작하는 모든 숫자가 0으로 변환되어 첫 번째 0이 발견되고 이 0이 1로 뒤집힐 때까지 볼 수 있습니다. 이제 이 논리에 대한 알고리즘을 생성해 보겠습니다.
알고리즘
Step 1 : Start right to left i.e n-1 to 0 Step 2 : If 0 is encountered, change it 1 and break Step 3 : If one is encounter change it to 0. Step 4 : When no zero is encountered, add 1 to the start of the array. Step 5 : Print the array.
예시
이제 이 알고리즘의 코드 구현을 살펴보겠습니다.
#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';
flag = 1;
break;
} else
num.at(i) = '0';
}
if (flag < 0)
num = "1" + num;
return num;
}
int main() {
string number = "0111010111";
cout<<"The Binary representation of the number is "<<number<<endl;
cout<<"Binary representation of next number is "<<nextBinary(number);
return 0;
} 출력
The Binary representation of the number is 0111010111 Binary representation of next number is 0111011000