PHÉP CÔNG NHỊ PHÂN BẰNG PHÉP XOR

PHÉP CÔNG NHỊ PHÂN BẰNG PHÉP XOR

Chào mọi người! Hôm nay, mình xin giới thiệu giải thuật cộng 2 số nhị phân, lấy ý tưởng dựa trên các phép bit đơn giản (and, or, xor, not), cụ thể là phép XOR.

Phép XOR
Bảng chân trị:

Giá trị phép XOR bằng 0 khi cả hai chân trị đầu vào giống nhau, điều này đúng với N chân trị đầu vào có cùng chân trị, ví dụ: 0 xor 0 xor 0 ... xor 0 = 0, nhưng không đúng với 1 xor 0 xor 0 ... = ?

Bài toán phép cộng:
Khi ta cộng 2 số nhị phân, ta sẽ lần lượt cộng các số từ phải sang trái, dựa trên bản chân trị:

+ 0     1
0     0   1
1   1   10

Với 1 + 1 = 10 ta viết 0 và nhớ 1
Tức khi ký số KetQua[i] = A[i] + B[i] + Nho
nếu KetQua[i] >= 10 thì Nho = 1; KetQua[i] = KetQua[i] % 10; (%: chia lấy dư)
ngược lại Nho = 0;

Mối liên hệ giữa phép cộng Bit và Phép XOR

Ta có bản so sánh sau:

  Từ bản trên ta rút ra nhận xét:
KetQua[i] = A[i] xor B[i] xor Nho;
Nho = 1, nếu A[i] + B[i] + Nho > 1;
Nho = 0, ngược lại;

CODE (c++)

void Cong(bool A[], bool B[], bool KQ[])
{
  bool Nho = 0;
for (int i = SOBIT - 1; i > -1; i--)
{
KQ[i] = A[i] ^ B[i] ^ Nho; // Trong C++, phép XOR được ký hiệu là ^
if (A[i] + B[i] + Nho < 2)
Nho = 0;
else Nho = 1;
  }
}

Các bạn có thể xem code tường minh hơn ở đây.

Ngựa Sông