Trong bài toán này, cho biểu diễn nhị phân của một số, cần tìm biểu diễn nhị phân của số tiếp theo, tức là số kết quả sau khi cộng 1 vào số cho trước.
Biểu diễn nhị phân của một số là đổi cơ số sang cơ số 2 và biểu diễn số chỉ dùng 0 hoặc 1.
Ví dụ, biểu diễn nhị phân của 14 là 1110.
Vì vậy, ở đây ta được cho một số, giả sử n ở dạng nhị phân. Cần tìm biểu diễn nhị phân của n+1.
Để giải bài toán này, cần biết cơ bản của phép cộng nhị phân. Hãy xem gì xảy ra khi 1 cộng với 0 hoặc 1 trong dạng nhị phân:
0 + 1 = 1
1 + 1 = 10
Ví dụ
Hãy xem ví dụ cách giải bài toán trên:
Input: 010010111 Output: 010011000 Giải thích: (010010111)₂ là biểu diễn nhị phân của 152 và số tiếp theo là 153 biểu diễn nhị phân là (010011000)₂. Ta dùng phép cộng nhị phân và cộng (1)₂ vào biểu diễn nhị phân của số.
Từ ví dụ trên, thấy khi cộng nhị phân 1 vào số, tất cả các 1 bắt đầu từ phải chuyển thành 0, cho đến khi gặp 0 đầu tiên và 0 này được lật thành 1. Bây giờ hãy tạo thuật toán cho logic này.
Thuật toán
Bước 1: Bắt đầu từ phải sang trái, từ n-1 đến 0 Bước 2: Nếu gặp 0, đổi thành 1 và dừng Bước 3: Nếu gặp 1, đổi thành 0 Bước 4: Khi không gặp 0 nào, thêm 1 vào đầu mảng Bước 5: In mảng
Ví dụ
Triển khai mã dựa trên 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<<"Biểu diễn nhị phân của số là "<<number<<endl;
cout<<"Biểu diễn nhị phân của số tiếp theo là "<<nextBinary(number);
return 0;
}
Kết quả
Biểu diễn nhị phân của số là 0111010111 Biểu diễn nhị phân của số tiếp theo là 0111011000