Trong bài toán này, chúng ta được đưa ra biểu diễn nhị phân của một số và chúng ta phải tìm biểu diễn nhị phân của số tiếp theo, tức là số được tạo ra sau khi thêm một vào số đã cho.
Biểu diễn nhị phân của một số đang thay đổi cơ số của số thành cơ số 2 và đại diện cho số chỉ sử dụng 0 hoặc 1.
Ví dụ:biểu diễn nhị phân của 14 là 1110.
Vì vậy, ở đây chúng ta sẽ được cung cấp một số, giả sử n ở dạng nhị phân. Và chúng ta phải tìm biểu diễn nhị phân của n + 1.
Để giải quyết vấn đề này, chúng ta cần biết những điều cơ bản về phép cộng nhị phân. Hãy xem điều gì sẽ xảy ra khi 1 được thêm vào 0 hoặc 1 ở dạng nhị phân.
0 + 1 =1
1 + 1 =10
Ví dụ
Hãy xem một ví dụ về cách giải quyết vấn đề trên,
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.
Từ ví dụ trên, chúng ta có thể thấy rằng khi thêm số nhị phân 1 vào số, tất cả những cái bắt đầu từ bên phải được chuyển đổi thành 0, cho đến khi gặp số 0 đầu tiên và số 0 này được chuyển thành 1. Bây giờ hãy tạo một thuật toán cho logic này.
Thuật toán
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.
Ví dụ
Bây giờ, hãy xem việc triển khai mã của thuật toán này.
#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;
} Đầu ra
The Binary representation of the number is 0111010111 Binary representation of next number is 0111011000