XOR

Giới thiệu

• Gần đây tôi có dịp giải thích toán tử XOR. Trước đây, việc học XOR là bắt buộc để thao tác bit mức thấp trên máy tính, nhưng ngày nay với lập trình viên cấp cao thì nó đã trở thành tùy chọn.
• Trong quá trình chuẩn bị một bài giảng về XOR, tôi đã hệ thống lại nhiều suy nghĩ khác nhau và quyết định lưu chúng thành tài liệu.

Logic Boolean của XOR

XOR là gì?

• XOR là một toán tử logic nhận hai bit đầu vào và xuất ra một bit.
• Có thể giải thích cách XOR hoạt động thông qua bảng chân trị.

"OR loại trừ"

• XOR có nghĩa là "OR loại trừ", và trả về đúng khi chỉ một trong hai đầu vào là đúng.

Toán tử 'không bằng'

• Vì XOR trả về 1 khi hai đầu vào khác nhau, nên nó hoạt động giống hệt a ≠ b.

Đảo có điều kiện

• Có thể xem XOR như một phép đảo có điều kiện, trong đó một đầu vào quyết định có đảo đầu vào còn lại hay không.

Chẵn lẻ, hoặc phần dư khi chia cho 2

• XOR trả về 1 khi có số lượng bit đúng là số lẻ trong các đầu vào.

Hiệu modulo 2

• XOR hoạt động giống hệt phần dư của phép cộng và phép trừ khi chia cho 2.

Tính chất của XOR

• XOR tuân theo tính giao hoán và kết hợp, 0 đóng vai trò là phần tử đơn vị, và mọi đầu vào đều là nghịch đảo của chính nó.

XOR theo bit trên số nguyên

• Có thể biểu diễn số nguyên ở dạng nhị phân và thực hiện phép XOR theo từng bit.
• XOR theo bit có cùng các tính chất với XOR Boolean.

Ứng dụng của XOR

Mã hóa: kết hợp bản rõ và keystream

• XOR được dùng trong mã hóa để kết hợp bản rõ với keystream.
• XOR đơn giản hơn phép cộng trong phần cứng nên hiệu quả hơn.

Đồ họa pixel: vẽ hình có thể xóa dễ dàng

• Trong đồ họa máy tính thập niên 1980, XOR được dùng để vẽ những hình có thể xóa dễ dàng.
• Khi dùng XOR, có thể vẽ lại pixel để khôi phục trạng thái ban đầu.

"Danh tính half adder"

• XOR biểu thị bit thấp của phép cộng, còn AND biểu thị bit cao.
• Có thể dùng XOR và AND để thực hiện phép cộng trên số nguyên.

Tài liệu này giải thích nhiều tính chất và ứng dụng khác nhau của XOR, đồng thời giúp hiểu cách XOR hoạt động và những nơi nó có thể được sử dụng hữu ích.