이 문제에서는 숫자의 이진 표현이 주어지고 이전 숫자의 이진 표현, 즉 주어진 숫자에서 1을 뺀 결과를 찾아야 합니다.
이진 표현 의 수는 수의 밑수를 2로 변경하고 0 또는 1만 사용하여 숫자를 나타내는 것입니다.
예를 들어, 23의 이진 표현은 10111입니다.
따라서 여기에 숫자가 주어집니다. n을 이진 형식으로 가정해 보겠습니다. 그리고 우리는 n-1의 이진 표현을 찾아야 합니다.
이 문제를 해결하려면 이진 빼기의 기본 사항을 알아야 합니다. 이진 형식으로 0 또는 1에서 1을 뺄 때 어떤 일이 발생하는지 봅시다. 0 - 1 =1 + 1 다음 비트에서 캐리. 1 - 1 =0.
문제를 더 잘 이해하기 위해 예를 들어 보겠습니다.
Input : 101101100 Output : 101101011 Explanation : (101101100)2 Is the binary representation of 364. The number preceding it is 363 whose binary representation is (101101011)2 . we have used binary subtraction here and subtracted (1)2 from the binary representation of the number to yield the result .
이 프로그램 뒤에 있는 논리를 살펴보고 우리의 논리를 기반으로 알고리즘을 설계할 것입니다. 여기서 숫자의 이진 표현에서 1을 빼야 합니다. 이를 위해 오른쪽에서 시작하여 1이 나타날 때까지 모든 0을 1로 뒤집습니다. 1이 발생하면 1을 0으로 뒤집고 최종 결과를 반환합니다.
알고리즘
Step 1 : Start right to left i.e n-1 to 0. Step 2 : If 1 is encounter change it to 0 and break. Step 3 : If 0 is encountered, change it 1. Step 4 : Print the array.
예시
위 알고리즘의 프로그램 구현 -
#include <bits/stdc++.h>
using namespace std;
string previousNumber(string num) {
int n = num.size();
if (num.compare("1") == 0)
return "0";
int i;
for (i = n - 1; i >= 0; i--) {
if (num.at(i) == '1') {
num.at(i) = '0';
break;
} else
num.at(i) = '1';
}
if (i == 0)
return num.substr(1, n - 1);
return num;
}
int main() {
string number = "1011011000";
cout<<"the Binary representation of the number is "<<number<<endl;
cout<<"Binary representation of previous number is "<<previousNumber(number);
return 0;
} 출력
The Binary representation of the number is 1011011000 Binary representation of previous number is 1011010111