Trong phần này, chúng ta sẽ xem cách chúng ta có thể tìm phần bù của 2 bằng cách sử dụng phép toán XOR trên một chuỗi nhị phân. Phần bổ sung của 2 thực sự là phần bổ sung của 1 + 1. Chúng tôi sẽ sử dụng phép toán XOR để lấy phần bổ sung của 1.
Chúng tôi sẽ duyệt qua chuỗi từ LSb và tìm 0. Chúng tôi sẽ lật tất cả các số 1 thành 0 cho đến khi nhận được số 0. Sau đó lật số 0.
Chúng tôi sẽ đi ngang từ LSb. Sau đó, bỏ qua tất cả các số 0 cho đến khi chúng tôi nhận được 1. Bỏ qua số 1 đầu tiên, chúng tôi sẽ chuyển đổi tất cả các bit bằng phép toán XOR.
Thuật toán
get2sComp (bin)
begin len := length of the binary string flag := false for i := len-1 down to 0, do if bin[i] is 0, and flag is not set, then ignore the next part, jump to next iteration else if flag is set, then bin[i] := flip of bin[i] end if flag := true end if done if the flag is not set, then attach 1 with bin and return else return bin end if end
Ví dụ
#include <iostream>
using namespace std;
string get2sComplement(string bin) {
int n = bin.length();
bool flag = false; //flag is used if 1 is seen
for (int i = n - 1; i >= 0; i--) { //traverse from last bit
if (bin[i] == '0' && !flag) {
continue;
} else {
if (flag)
bin[i] = (bin[i] - '0') ^ 1 + '0'; //flip bit using XOR, then convert to ASCII
flag = true;
}
}
if (!flag) //if no 1 is there, just insert 1
return "1" + bin;
else
return bin;
}
int main() {
string str;
cout << "Enter a binary string: ";
cin >> str;
cout << "2's complement of " << str <<" is " << get2sComplement(str);
} Đầu ra
Enter a binary string: 10110110 2's complement of 10110110 is 01001010