2's Complement ของสตริงไบนารีโดยใช้ XOR

ในส่วนนี้เราจะดูวิธีหา 2's complement โดยใช้การดำเนินการ XOR บนสตริงไบนารี 2's complement จริงๆ แล้วคือ 1's complement + 1 เราจะใช้ XOR เพื่อหา 1's complement

เราจะวนลูปจาก LSB มองหา 0 จะพลิก 1 ทั้งหมดเป็น 0 จนกว่าจะเจอ 0 แล้วค่อยพลิก 0 ตัวนั้น

จะวนจาก LSB แล้วข้าม 0 ทั้งหมดจนเจอ 1 ข้าม 1 ตัวแรก แล้วค่อย toggle ทุกบิตโดยใช้ XOR

อัลกอริทึม

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

ตัวอย่างโค้ด

#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'; flag = true; } } if (!flag) 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); }

ผลลัพธ์

Enter a binary string: 10110110 2's complement of 10110110 is 01001010