Bù 2 của chuỗi nhị phân dùng XOR

Phần này hướng dẫn tìm bù 2 của chuỗi nhị phân bằng phép XOR. Bù 2 = bù 1 + 1. Ta dùng XOR để lấy bù 1.

Thuật toán: Duyệt từ bit thấp nhất (LSB), tìm bit 0 đầu tiên. Đảo tất cả bit 1 thành 0 cho đến khi gặp 0, rồi đảo bit 0 đó.

Thuật toán get2sComp(bin)

begin
    len := độ dài chuỗi nhị phân
    flag := false
    for i := len-1 down to 0:
        nếu bin[i] là 0 và flag chưa set:
            bỏ qua, sang vòng lặp tiếp
        ngược lại:
            nếu flag đã set:
                bin[i] := đảo bit bin[i]
            kết thúc nếu
            flag := true
        kết thúc nếu
    kết thúc for
    nếu flag chưa set:
        thêm '1' vào đầu bin và trả về
    ngược lại:
        trả về bin
    kết thúc nếu
end

Ví dụ code

#include <iostream>
using namespace std;

string get2sComplement(string bin) {
    int n = bin.length();
    bool flag = false;
    for (int i = n - 1; i >= 0; i--) {
        if (bin[i] == '0' && !flag) {
            continue;
        } else {
            if (flag)
                bin[i] = (bin[i] - '0') ^ 1 + '0'; // XOR đảo bit
            flag = true;
        }
    }
    if (!flag)
        return "1" + bin;
    else
        return bin;
}

int main() {
    string str;
    cout << "Nhap chuoi nhi phan: ";
    cin >> str;
    cout << "Bu 2 cua " << str << " la " << get2sComplement(str);
    return 0;
}

Kết quả

Nhap chuoi nhi phan: 10110110
Bu 2 cua 10110110 la 01001010