Biểu diễn nhị phân của số trước đó trong C++

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ố trước đó, tức là số kết quả sau khi trừ 1 từ 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 23 là 10111.

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 trừ nhị phân. Hãy xem gì xảy ra khi 1 trừ từ 0 hoặc 1 trong dạng nhị phân: 0 - 1 = 1 + 1 mượn từ bit tiếp theo. 1 - 1 = 0.

Hãy lấy ví dụ để hiểu rõ hơn:

Input: 101101100
Output: 101101011
Giải thích: (101101100)₂ là biểu diễn nhị phân của 364. Số trước đó là 363 biểu diễn nhị phân là (101101011)₂. Ta dùng phép trừ nhị phân và trừ (1)₂ từ biểu diễn nhị phân của số để ra kết quả.

Hãy xem logic đằng sau chương trình này và thiết kế thuật toán dựa trên logic đó. Ở đây cần trừ 1 từ biểu diễn nhị phân của số. Với điều này, bắt đầu từ phải sang trái và lật tất cả 0 thành 1 cho đến khi gặp 1. Khi gặp 1, lật 1 thành 0 và trả về kết quả cuối cùng.

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 1, đổi thành 0 và dừng.
Bước 3: Nếu gặp 0, đổi thành 1.
Bước 4: In mảng.

Ví dụ

Triển khai chương trình dựa trên thuật toán trên:

#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<<"Biểu diễn nhị phân của số là "<<number<<endl;
    cout<<"Biểu diễn nhị phân của số trước đó là "<<previousNumber(number);
    return 0;
}

Kết quả

Biểu diễn nhị phân của số là 1011011000
Biểu diễn nhị phân của số trước đó là 1011010111