XOR

 (chiark.greenend.org.uk)
1 điểm bởi GN⁺ 2025-02-19 | 1 bình luận | Chia sẻ qua WhatsApp
  • XOR là phép toán cho ra 1 khi hai bit khác nhau, và có thể được hiểu như một cách thống nhất giữa OR loại trừ, phép khác nhau, đảo điều kiện, và phép cộng/trừ mod 2
  • XOR theo bit trên số nguyên xử lý từng vị trí độc lập để làm lộ ra sự khác biệt theo từng bit, hoạt động như phép cộng nhị phân không nhớ đồng thời giữ các tính chất giao hoán, kết hợp, phần tử đơn vị 0, và phần tử nghịch đảo của chính nó
  • Trong mật mã, nó được dùng để kết hợp bản rõ với keystream, còn trong đồ họa pixel thời trước, người ta dùng cách vẽ lại cùng một hình để xóa nó nhằm giảm tải bộ nhớ và CPU
  • Các tính chất của XOR được tận dụng trực tiếp trong những phép tính tạo ra khác biệt rồi lại triệt tiêu nó, như đẳng thức half-adder, hoán đổi bit, XOR swap ba bước, hay điều kiện thắng trong trò chơi Nim
  • Nó còn nối tiếp sang hiệu đối xứng của tập hợp, nhóm có số mũ 2, nim-sum, đại số tuyến tính và đa thức trên GF(2), đồng thời liên hệ với các kỹ thuật phát hiện/sửa lỗi và mật mã như Hamming code, CRC, AES, GCM, và Classic McEliece

Ý nghĩa cơ bản của XOR

  • XOR là một phép toán Boolean có hai bit đầu vào và một bit đầu ra, với bảng chân trị là 00→0, 01→1, 10→1, 11→0
  • Nếu nhìn như “exclusive OR”, nó cho ra 1 khi chỉ một trong hai đầu vào là đúng, còn nếu cả hai đều đúng thì cho ra 0
  • Nếu nhìn như “not equals”, thì a XOR b tương đương với a ≠ b, nên cho ra 1 khi hai giá trị Boolean khác nhau
  • Nếu nhìn như đảo điều kiện, thì khi a=0 nó giữ nguyên b, còn khi a=1 thì nó đảo b
    • Vì cùng lý do đó, cũng có thể hiểu theo chiều lấy b làm đầu vào điều khiển và đảo a
  • Theo góc nhìn parity, nó cho biết số lượng bit 1 trong các đầu vào là lẻ hay chẵn
    • Với hai bit, nó bằng a+b mod 2
    • Nó cũng bằng a-b mod 2
    • Khi XOR nhiều giá trị, ta biết tổng số bit 1 trong toàn bộ đầu vào là lẻ hay chẵn

Tính chất đại số của XOR

  • XOR thỏa mãn tính giao hoán và tính kết hợp
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • Trong một danh sách XOR dài, thứ tự và cách nhóm không ảnh hưởng đến kết quả
  • 0 là phần tử đơn vị của XOR
    • a XOR 0 = 0 XOR a = a
    • Trong một danh sách XOR dài, có thể bỏ các số 0 đi
  • Mọi giá trị đều là nghịch đảo của chính nó
    • a XOR a = 0
    • Nếu cùng một biến xuất hiện hai lần thì có thể khử cả hai hạng đó cùng nhau
    • Có thể loại bỏ một hạng đã biết khỏi giá trị đã trộn, như trong (a XOR b) XOR b = a, bằng cách XOR thêm hạng đó một lần nữa

XOR theo bit trên số nguyên

  • XOR theo bit của số nguyên lấy hai số nguyên dưới dạng nhị phân rồi XOR từng bit ở từng vị trí một cách độc lập
  • Các tính chất của XOR trên một bit vẫn giữ nguyên với số nguyên
    • a XOR b = b XOR a
    • (a XOR b) XOR c = a XOR (b XOR c)
    • a XOR 0 = a
    • a XOR a = 0
  • XOR theo bit cho biết sự khác biệt theo từng bit giữa hai số nguyên
    • Nếu a=b thì a XOR b = 0
    • Nếu a≠b thì có ít nhất một bit khác nhau nên a XOR b ≠ 0
    • Các bit 1 trong kết quả cho biết các vị trí mà hai đầu vào khác nhau
  • XOR theo bit cũng có thể được xem là bộ đảo bit có điều kiện
    • Nó chỉ đảo bit dữ liệu tại những vị trí mà giá trị điều khiển có bit 1
    • Trong ASCII và một số bảng mã kế tiếp, chữ cái Latin hoa và thường chỉ khác nhau đúng một bit, nên có thể XOR giá trị ký tự với 32 để đổi hoa/thường
    • Quy tắc này không áp dụng cho mọi ký tự Unicode, và nhiều ký tự không có khái niệm hoa/thường hoặc không tuân theo quy tắc đó
  • XOR theo bit tương đương với phép cộng nhị phân không nhớ
    • Nó chỉ cộng mod 2 ở từng vị trí và không truyền bit nhớ sang vị trí kế tiếp

XOR trong mật mã

  • Trong mật mã, người ta tạo ra một keystream có cùng độ dài với bản rõ, rồi kết hợp các byte hoặc word của bản rõ với keystream để tạo bản mã
  • Ở bước kết hợp này, XOR thường được sử dụng
    • Bên nhận có thể XOR lại với cùng keystream để khôi phục bản rõ ban đầu
    • Việc bên gửi và bên nhận dùng cùng một phép toán cũng tiện lợi hơn đôi chút
  • Cách tạo ra chính keystream có thể phức tạp hơn
    • one-time pad dùng dữ liệu thật sự ngẫu nhiên với kích thước bằng toàn bộ thông điệp, nên không thể bị phá nhưng rất thiếu thực tế cho hầu hết mục đích
    • Thông thường, stream cipher hoặc block cipher chạy ở counter mode sẽ tạo keystream dài cần thiết từ một khóa nhỏ
  • Cách này có thể cung cấp tính bí mật nếu keystream tốt, nhưng không cung cấp tính toàn vẹn để phát hiện sửa đổi thông điệp
    • Bảo vệ toàn vẹn là một vấn đề riêng biệt
    • Việc bỏ qua toàn vẹn là sai lầm phổ biến trong thiết kế hệ mật của người mới bắt đầu, và cũng dẫn đến hậu quả sai trong cả các cơ chế mã hóa phức tạp hơn
  • Trong phần cứng, XOR đơn giản hơn phép cộng
    • Phép cộng cần lan truyền bit nhớ giữa các bit nên tốn diện tích chip và thời gian hơn
    • XOR không có bit nhớ nên rẻ hơn trong mạch chuyên dụng

XOR drawing và đồ họa pixel

  • Các máy tính gia đình thập niên 1980 bị hạn chế về số bit trên mỗi pixel màn hình và dung lượng RAM, nên khó lưu trữ hai bản đầy đủ của cả màn hình
  • Nếu vẽ vật thể chuyển động bằng XOR, chỉ cần vẽ lại đúng vật thể đó là có thể khôi phục màn hình gốc
    • Lấy giá trị pixel màn hình S XOR với pixel của vật thể chuyển động M để tạo C, rồi sau đó XOR lại với cùng M để khôi phục S
  • Trên các màn hình mà nhiều pixel được packed vào một byte hoặc dùng cấu trúc bit plane, việc tổng hợp bằng phép cộng khá rắc rối
    • Phép cộng thông thường có thể làm bit nhớ từ một pixel tràn sang pixel kế tiếp
    • XOR hoàn toàn không có bit nhớ nên không gặp vấn đề đó
  • Nếu vẽ đường bằng XOR, các pixel nơi hai đường cắt nhau sẽ bị đảo hai lần và quay về màu nền, nên có thể trông như một vết khuyết nhỏ
    • Vết khuyết này được chấp nhận như cái giá phải trả để khi xóa một đường thì không phá hỏng đường còn lại
  • XOR drawing cũng thuận lợi cho hoạt hình đơn giản
    • Vẽ thêm một đường mới và vẽ lại một đường cũ để xóa nó là đã có khung hình tiếp theo
    • Không cần vẽ lại mọi pixel hiện có trên màn hình hay mọi đường thẳng, nên tiết kiệm bộ nhớ và CPU
    • Đường chuyển động trong game Qix năm 1981 và cả đường viền khi di chuyển cửa sổ trong GUI đời đầu đều dùng cách này

Đẳng thức half-adder

  • Trong phép cộng một bit, bit thấp của a+b là a XOR b, còn bit cao là a AND b
  • Quan hệ tương tự cũng đúng với các phép toán theo bit trên số nguyên
    • a + b = (a XOR b) + 2 × (a AND b)
    • a XOR b là giá trị được cộng mà không có bit nhớ, còn a AND b chứa các bit nhớ lẽ ra phải phát sinh ở từng vị trí
  • Quan hệ này có thể được xem là đẳng thức half-adder
    • Half-adder phần cứng dùng cổng AND và XOR để tạo bit nhớ và bit thấp của phép cộng hai bit
    • Nó không có nghĩa là phép cộng số nguyên đầy đủ được tạo ra chỉ bằng những phép toán đơn giản đó, vì dấu + ở vế phải vẫn hoàn tất việc lan truyền bit nhớ
  • Có thể dùng đẳng thức này để tính trung bình của hai số nguyên mà không bị tràn số
    • Nếu chỉ làm a+b rồi dịch phải thì có thể làm mất bit cao nhất của tổng 33 bit
    • Trên các CPU không có carry flag hoặc có nhưng bất tiện, hay thiếu lệnh như RRX/RCR, dạng (a XOR b) >> 1 + (a AND b) là một lựa chọn thay thế
    • Ví dụ như MIPS, RISC-V, DEC Alpha không có carry flag, còn Arm Thumb đời đầu thiếu RRX
  • Trên CPU không có lệnh XOR, có thể đảo ngược đẳng thức này để tạo XOR
    • a XOR b = (a + b) − 2 × (a AND b)
    • CPU Data General trong thập niên 1970 có AND nhưng không có bitwise XOR

Hoán đổi bit và giá trị

  • Bài toán đổi chỗ hai bit có thể rút gọn thành: nếu hai bit giống nhau thì không cần làm gì, còn nếu khác nhau thì đảo cả hai bit
  • Dùng XOR và shift, ta có thể tìm xem hai bit có khác nhau không rồi đảo cả hai vị trí nếu cần
    • diff_all = input XOR (input >> distance) tính sự khác biệt giữa các cặp bit cách nhau một khoảng cố định
    • Dùng AND để lọc ra chỉ những vị trí quan tâm
    • Sau đó sao chép phần khác biệt đã chọn sang vị trí còn lại rồi XOR vào đầu vào để chỉ đảo hai bit khi cần
  • Cùng cách đó cũng có thể dùng để đổi nhiều cặp bit cùng khoảng cách trong một lần
    • Thay vì một bit mask đơn lẻ, ta dùng mask chứa nhiều bit
    • Beneš network có thể biểu diễn một hoán vị bất kỳ bằng cách hoán đổi nhiều cặp cùng khoảng cách qua nhiều giai đoạn
  • Cũng có thể hoán đổi cả hai giá trị bằng XOR swap ba bước
    • a = a XOR b
    • b = b XOR a
    • a = a XOR b
    • Không cần biến tạm mà vẫn đổi chỗ được hai giá trị
  • XOR swap ba bước có vấn đề aliasing
    • Nó hoạt động khi đổi hai biến khác nhau
    • Nếu hai tên cùng trỏ đến một vị trí lưu trữ, như khi đổi một phần tử mảng với chính nó, giá trị có thể trở thành 0

Trò chơi Nim và XOR

  • Nim là trò chơi có nhiều đống, mỗi lượt người chơi chọn một đống và lấy đi ít nhất 1 quân với số lượng tùy ý; ai không còn nước đi thì thua
  • Trong phiên bản Nim đơn giản, vị trí thua là vị trí mà XOR theo bit của kích thước tất cả các đống bằng 0
  • Nếu tổng XOR đang là 0 mà thay kích thước một đống từ a thành giá trị khác b, thì tổng XOR sẽ thay đổi đi a XOR b; vì a≠b nên kết quả sẽ khác 0
  • Khi tổng XOR khác 0, ta nhìn vào bit 1 cao nhất của giá trị XOR tổng x, rồi chọn một đống có bit đó bằng 1 và giảm nó xuống pile XOR x để đưa tổng XOR về 0
  • Ví dụ, các đống có kích thước 12, 10, 3 tương ứng với nhị phân 1100, 1010, 0011, và XOR là 0101
    • Chỉ đống lớn nhất 12 khi XOR với 0101 mới giảm xuống còn 9
    • Nước đi thắng là lấy 3 quân khỏi 12 để biến nó thành 9

Các cấu trúc toán học trông giống XOR

  • Trong lý thuyết tập hợp, hiệu đối xứng X∆Y là phép toán chứa một phần tử nếu nó thuộc đúng một trong hai tập
    • Nếu xem việc thuộc tập là một giá trị Boolean, thì hiệu đối xứng chính là XOR
    • Vì vậy nó chia sẻ các tính chất của XOR như giao hoán và kết hợp
  • Trong lý thuyết nhóm, nhóm có số mũ 2 là nhóm mà mọi phần tử đều là nghịch đảo của chính nó
    • Phép toán trong nhóm như vậy thỏa tính kết hợp, và theo một bài tập kinh điển thì cũng suy ra tính giao hoán
    • Việc hai phần tử giống nhau đứng cạnh nhau thì triệt tiêu nhau khiến nó giống XOR
    • Mọi nhóm có số mũ 2 đều có thể được hiểu như dạng XOR theo bit của các hàm nhận giá trị {0,1}
  • Trong phân tích Sprague-Grundy, nhiều vị trí của impartial game được gán một Grundy number
    • Grundy number của một tổ hợp gồm nhiều trò con được tính bằng XOR theo bit của Grundy number của từng trò thành phần
    • Trong game theory, XOR theo bit của các số nguyên không âm cũng thường được gọi là nim-sum
  • Trường GF(2) là trường hữu hạn chỉ có hai phần tử 0 và 1
    • Phép cộng và phép trừ hoạt động như XOR
    • Phép nhân hoạt động như AND
    • Vì vậy a AND (b XOR c) = (a AND b) XOR (a AND c) luôn đúng

Đại số tuyến tính trên GF(2) và sửa lỗi

  • Vector và ma trận trên GF(2) là các cấu trúc có thành phần 0 hoặc 1, và phép cộng vector hay ma trận là XOR theo từng thành phần
  • Nhân ma trận M với vector v tương đương với việc XOR các cột của M được chọn bởi các thành phần 1 trong v
  • Mã sửa lỗi mở rộng thông điệp m bit thành codeword n bit dài hơn để có thể phát hiện hoặc sửa một số lỗi bit
    • Nếu các codeword hợp lệ khác nhau ở nhiều bit, thì một số ít lỗi bit sẽ không biến codeword này thành một codeword hợp lệ khác
    • Nếu hai codeword hợp lệ khác nhau tối thiểu k bit thì có thể phát hiện dưới k lỗi và sửa dưới k/2 lỗi bằng cách tìm codeword gần nhất
  • Mã tuyến tính dùng generator matrix và check matrix trên GF(2)
    • sender dùng generator matrix để mở rộng thông điệp m bit thành codeword n bit
    • receiver dùng check matrix để xác nhận codeword nhận được có hợp lệ hay không, và nếu có lỗi thì thu được syndrome
    • Cùng một mẫu lỗi sẽ sinh ra cùng một syndrome bất kể thông điệp là gì
  • Hamming code là ví dụ với độ dài mã n bằng 2^d−1
    • Nếu n=15, các vị trí bit từ 0001 đến 1111 được đánh số bằng các số 4 bit khác 0
    • Bên nhận XOR tất cả các chỉ số của những bit đang là 1; nếu kết quả bằng 0 thì đó là codeword hợp lệ
    • Nếu một bit bị lật, kết quả XOR sẽ chính là chỉ số của bit bị lật, nên có thể sửa lỗi 1 bit mà không cần lookup table
    • Hamming code 15 bit chứa 11 bit dữ liệu và dùng 4 bit cho sửa lỗi

Đa thức trên GF(2), CRC, và các trường hữu hạn lớn hơn

  • Đa thức trên GF(2) là các đa thức hình thức có hệ số 0 hoặc 1, và phép cộng tương đương với XOR các hệ số cùng bậc
  • Phép nhân đa thức tạo ra các tích riêng như đa thức thông thường rồi rút gọn hệ số theo mod 2
    • Nếu xem biểu diễn này như chuỗi bit, nó giống phép nhân số nguyên nhưng khi cộng các tích riêng thì dùng XOR không nhớ thay vì phép cộng thông thường
    • x86 cung cấp lệnh nhân không nhớ như CLMUL, còn Arm có họ lệnh polynomial multiplication
  • CRC dùng phần dư của phép chia đa thức trên GF(2) làm checksum
    • Xem chuỗi bit của thông điệp gửi như một đa thức lớn M, rồi giữ phần dư M mod P khi chia cho đa thức đã thỏa thuận P
    • Cách này được dùng để kiểm tra packet mạng như Ethernet và các hệ tương tự
    • CRC không sửa lỗi mà chỉ phát hiện lỗi, phù hợp với các tình huống mà gần như mọi lần truyền đều bình thường và thỉnh thoảng mới có bit bị lật hoặc có nhiễu
  • Các trường hữu hạn lớn hơn có thể được tạo từ đa thức trên GF(p) bằng cấu trúc phần dư theo một irreducible polynomial Q
    • Nếu bậc của Q là d thì trường hữu hạn mới có p^d phần tử
    • Khi p=2, irreducible polynomial có thể được viết như các mẫu bit dưới dạng số nguyên, và dãy đó được đăng trong OEIS A014580
  • Các trường hữu hạn có kích thước là lũy thừa của 2 xuất hiện trong nhiều kỹ thuật mật mã
    • Trường hữu hạn kích thước 2^8 là thành phần cốt lõi của AES và Twofish
    • Trường hữu hạn kích thước 2^128 được dùng trong GCM để kết hợp mã hóa khối lượng lớn với bảo vệ toàn vẹn
    • Các trường hữu hạn kích thước là lũy thừa của 2 cũng xuất hiện trong một số dạng elliptic-curve cryptography và trong thuật toán giải mã của cơ chế hậu lượng tử Classic McEliece

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-02-19
Ý kiến trên Hacker News

  • Kỹ thuật XOR bị nguyền rủa mà tôi thích là danh sách liên kết đôi XOR: https://en.m.wikipedia.org/wiki/XOR_linked_list
    Thay vì mỗi nút lưu riêng con trỏ next/previous, nó lưu một giá trị duy nhất là XOR của cả hai. Tất nhiên đó là một con trỏ không hợp lệ, nhưng khi duyệt, XOR con trỏ của nút trước với con trỏ kết hợp đó sẽ cho ra con trỏ của nút tiếp theo, và cũng có thể duyệt hai chiều. Cảm giác như phạm pháp vậy

    • So với danh sách liên kết đôi thông thường, bạn mất khả năng xóa phần tử đó khi chỉ có địa chỉ của phần tử, hoặc chỉ có một iterator ổn định qua thao tác chèn/xóa. Mà đây thường là lý do cốt lõi để dùng danh sách liên kết đôi
      Một nhược điểm ít bản chất hơn là viết danh sách liên kết XOR trong C tuân thủ nghiêm ngặt chuẩn thì cực kỳ phiền. Chuẩn không đảm bảo rằng khi ép cùng một con trỏ sang số nguyên thì sẽ ra cùng một số nguyên, nên trên thực tế phải biến mọi thứ thành uintptr_t để duy trì phiên bản ép kiểu số nguyên đã chuẩn hóa
    • Ngay cả trên bộ xử lý 64-bit, nếu giả định hầu hết ứng dụng chỉ cần dưới 4GB RAM, thì có thể giảm thêm dung lượng lưu trữ chỉ bằng không gian địa chỉ 32-bit
      Đi xa hơn nữa, có lẽ con trỏ gần/tương đối 16-bit cũng khả thi. Nó có thể hợp với thiết kế hướng dữ liệu: đặt các khối 64K phần tử, rồi trỏ tới phần tử bên trong bằng chỉ mục uint16
    • Làm vậy thì garbage collector sẽ ghét lắm. Hoặc ít nhất nó sẽ coi cấu trúc dữ liệu này là rác
    • Tôi tò mò vì sao người ta lại muốn dùng kỹ thuật này
    • Cái này không khác mấy việc lưu hiệu của hai con trỏ hơn là một con trỏ. Lưu hiệu thì đương nhiên cũng duyệt hai chiều được

  • Có một điểm bị bỏ sót. XOR cũng là hàm băm tuyến tính độc lập 3-wise, nên có thể dùng để lấy mẫu gần đều theo xác suất và đếm số nghiệm của hàm Boolean. Nó thật sự hữu ích, và được dùng để tạo các bộ đếm cho ra số lượng mang tính xác suất nhưng có chứng minh. Tôi đã viết một phần giải thích dễ hiểu hơn ở đây https://www.msoos.org/2018/12/how-approximate-model-counting...
    Về cơ bản, mỗi lần nó giảm không gian nghiệm gần như chính xác một nửa. Vì vậy cứ tiếp tục thêm điều kiện XOR cho đến khi, chẳng hạn, còn 10 nghiệm; nếu số điều kiện XOR đã thêm là k, thì chỉ cần nhân 10 với 2^k. Vì mỗi lần giảm một nửa nên đạt tới mức khoảng 10 nghiệm rất nhanh, do đó khả năng mở rộng tốt
    Các bài báo liên quan ở https://arxiv.org/abs/1306.5726 và https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf, còn công cụ ở https://github.com/meelgroup/approxmc và https://github.com/meelgroup/unigen. Trong cuộc thi model counting gần đây, khi kết hợp với bộ đếm chính xác, nó đã áp đảo các đối thủ khác; slide ở https://mccompetition.org/assets/files/2024/MC2024_awards.pd...

  • Một trong những giai thoại XOR tôi thích là câu chuyện của Bryan Cantrill từ Oxide, Joyent, Sun trong bài thuyết trình này https://speakerdeck.com/bcantrill/oral-tradition-in-software... và video này https://www.youtube.com/watch?v=4PaWFYm0kEw
    Tóm tắt để khỏi phải bấm link: khi còn ở Sun, ông nói chuyện với đồng nghiệp Roger Faulkner về lý do C không có XOR logic; Faulkner nói là vì không thể đánh giá ngắn mạch, còn Brian thì thấy điều đó kỳ lạ. Thế là Roger gửi email hỏi Dennis Ritchie, và Ritchie xác nhận rằng Faulkner nói đúng. Cách Cantrill kể lại rất hài hước, nhưng điều đáng kinh ngạc là họ có thể hỏi trực tiếp chính người trong cuộc

    • DMR là một người thân thiện, hay giúp đỡ và dễ tiếp cận đến đáng ngạc nhiên. Khi còn là sinh viên đại học vào giữa thập niên 80, tôi đọc về trường hợp “đầu tiên” port Unix v6 sang Interdata 8/32 thay vì PDP-11, rồi liều gửi email tới dmr@research.att.com hỏi xem có thêm thông tin kiến trúc không
      Thời đó không có Google, thư viện đại học cũng không có tài liệu; vài ngày sau ông hỏi địa chỉ nhà, rồi vài tuần sau một bản sao sổ tay tóm tắt tập lệnh xuất hiện trong hộp thư của tôi. Nó mang cảm giác dòng IBM 360, và tôi vẫn còn giữ
    • C có XOR logic, chính là toán tử !=. Khác với các toán tử logic khác, nó cần chuẩn hóa đối số về một giá trị true duy nhất, và rất hợp với idiom chuyển đổi Boolean !! của C
    • Tôi không hiểu vì sao “vì không thể đánh giá ngắn mạch” lại là trở ngại cho việc thêm toán tử. Mong ai đó giải thích
    • Chủ đề đó bắt đầu từ 37:18
    • C đã có toán tử XOR bit ^ hơn 40 năm rồi: https://www.geeksforgeeks.org/bitwise-operators-in-c-cpp/

  • Hôm nay tôi mới biết rằng nếu XOR emoji ô tô với 0x20, tức là “chuyển sang chữ thường”, thì nó sẽ thành emoji cấm người đi bộ. Thấy trùng hợp đến mức quá khớp, nên tôi tò mò không biết có ai biết đây có phải là cố ý không
    Nếu suy diễn hơi quá thì cũng có thể nghĩ một cách kỳ lạ rằng chữ thường của emoji ô tô là biển báo ‘cấm người đi bộ’

    • Để tránh bộ xử lý bình luận loại bỏ emoji của HN, có thể kiểm tra như sau:
      >>> from unicodedata import lookup, name
      >>> name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20))
      'NO PEDESTRIANS'
    • Chữ thường của ô tô có lẽ nên là go-kart
    • Cũng có thể có :tada: → :tophat:, :rocket: → :mountain_cableway:

  • Một phép ẩn dụ đời thực hay để giải thích XOR là công tắc đèn trên cầu thang trong nhà. Có một công tắc ở dưới và một công tắc ở trên, cả hai cùng điều khiển một bóng đèn
    Ban đầu cả hai đều ở vị trí tắt; bật công tắc dưới thì đèn sáng. Đi lên cầu thang và bật công tắc trên thì dù cả hai công tắc đều ở vị trí “bật”, đèn lại tắt. Đèn chỉ sáng khi đúng một công tắc “bật” và công tắc kia “tắt”; các trường hợp khác thì tắt

    • Có khi thợ điện ở văn phòng chúng tôi đã đấu dây sai. Trong phòng có hai công tắc, nghĩ lại thì chúng hoạt động giống cổng AND hơn là XOR. Hai công tắc trong phòng khách thì chắc chắn hoạt động như XOR

  • Tôi thật sự không thích việc hàm logic này thường được gọi là XOR, tức “OR loại trừ”. Vì gần như lúc nào ý nghĩa thực sự cũng là “tổng lấy phần dư khi chia cho 2”, tức parity, chứ không phải OR loại trừ
    “Tổng lấy phần dư khi chia cho 2”/parity và “OR loại trừ” là hai hàm logic khác nhau, chỉ tình cờ trùng nhau khi có 2 toán hạng đầu vào. Bởi vì chỉ có một số lẻ không lớn hơn 2
    Khi có từ 3 đầu vào trở lên, thứ mà đa số gọi là XOR thực ra là parity: bằng 1 khi có số lượng lẻ đầu vào là 1. Trong khi đó, OR loại trừ là hàm chỉ bằng 1 khi có từ 3 đầu vào trở lên mà đúng một đầu vào là 1 và tất cả đầu vào còn lại là 0
    Trong phần cứng máy tính, parity quan trọng hơn OR loại trừ rất nhiều. Lý do chính là phép cộng lấy phần dư khi chia cho 2 được dùng làm khối dựng để triển khai phép cộng các số lớn hơn. Ngược lại, trong toán học, OR loại trừ quan trọng hơn parity rất nhiều
    Ví dụ, các lượng từ diễn tả rằng một vị từ đúng với một số phần tử, tất cả phần tử, hoặc đúng một phần tử duy nhất của một tập hợp lần lượt dựa trên OR, AND và OR loại trừ. “or” trong ngôn ngữ tự nhiên luôn có nghĩa là OR bao hàm hoặc OR loại trừ, chứ không phải parity mà nhiều lập trình viên gọi là XOR
    Trong lập trình, hiếm khi cần tính hàm logic OR loại trừ, nhưng nó lại thường được dùng để mô tả hành vi chương trình. Chẳng hạn như khi nói trong một cấu trúc ghép select/case/switch thì một trong câu lệnh thứ nhất, thứ hai hoặc thứ ba sẽ được thực thi; hoặc khi mô tả các kiểu mà giá trị hiện tại của một biến union/sum type có thể mang

    • Chuẩn ký hiệu kỹ thuật điện IEC 60617 xử lý phần này đúng cách. Cổng XOR được ký hiệu là =1, còn cổng parity là 2k + 1. Nhưng khi dùng phần mềm thiết kế mạch cho PCB hoặc FPGA, bạn vẫn có thể bị hớ vì nhận được thứ khác với mong đợi
    • Thứ được nói đến trong toán học được gọi là lượng từ tồn tại duy nhất, và có ký hiệu riêng là ∃!
    • Cần có cơ sở cho cách giải thích rằng khi có từ 3 đầu vào trở lên, “OR loại trừ” đúng khi chỉ đúng một đầu vào là 1
    • Cách diễn giải này cũng được bàn trong bài essay gốc

  • Cũng có bảng băm phân tán Kademlia: kademlia distributed hash table. Ý tưởng lớn là mỗi nút nhận các bit ngẫu nhiên trong phạm vi [0, 2^m), và khoảng cách được định nghĩa bằng XOR. Mục tiêu là tìm một thuật toán phân tán để nhanh chóng gửi thông tin từ X đến Y mà không cần biết toàn bộ mạng
    Chỉ nhìn toán học cũng có thể chứng minh nó hoạt động, nhưng trực giác trực quan tôi thích là thế này. Giả sử nút bắt đầu X muốn tìm nút k. Định nghĩa “cây khoảng cách-X” là một cây nhị phân có chỉ mục lá là 0, 1, 2..., và mỗi lá được gắn nhãn X^leaf_index để biểu thị khoảng cách tới X. Ví dụ vì dist(x, x) = x^x = 0, nhãn của nút gốc X nằm ở lá ngoài cùng bên trái 0
    Khoảng [2^i, 2^(i+1)) là một cây con nào đó trong cây khoảng cách-X. Nếu biết khoảng cách của k thuộc khoảng đó, ta truy vấn một nút Y nào đó trong đó làm hàng xóm xấp xỉ
    Dù chọn Y nào, trong cây khoảng cách-Y, tiền tố kết quả luôn là một hoán vị nào đó của cây con [2^i, 2^(i+1)) đã chọn trong cây khoảng cách-X. Chính xác hơn, có thể xem là labels_of_leaves_of_X([2^i, 2^(i+1))) == labels_of_leaves_of_Y([0, 2^i)). Chỉ mục dựa trên khoảng cách, nhưng nhãn có thể khác nhau
    Có rất nhiều tài liệu chặt chẽ hơn nhiều, cả về toán học lẫn thực nghiệm, khi so sánh với các bảng băm phân tán khác như Chord. Nhưng trực giác trực quan này cho ta cảm giác “tính đối xứng” của Kademlia là gì, và rằng mọi người đều có hàng xóm cục bộ của riêng mình cùng cây con của riêng mình
    Ngược lại, Chord dù triển khai hai chiều thì cũng tốn gấp đôi bộ nhớ, triển khai có vẻ rủi ro hơn, và khó đạt được mức “tách biệt” như vậy. Cửa sổ trượt hàng xóm kích thước S luôn di chuyển, và với mỗi bit có 2^m hàng xóm khác nhau. Dù phần lớn hàng xóm trông có vẻ giống nhau, nó vẫn không gọn gàng
    Kademlia có 1 + 2 + 4 ... + 2^m-1 hàng xóm, và toàn bộ được sắp xếp ngăn nắp

  • Thêm cho ai tò mò: người này chính là Simon Tatham trong Simon Tatham's Portable Puzzle Collection. Nếu chưa biết thì rất đáng thử khi rảnh rỗi offline
    Hồi cấp ba tôi đã đốt rất nhiều thời gian vào những trò này: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

  • Ngày nay, nhiều bộ giải tối ưu hóa tùy chỉnh, chẳng hạn như Ising Machine, dùng bài toán XOR làm benchmark. Thực ra, việc giải nhiều mệnh đề XOR có thể thực hiện trong thời gian đa thức bằng khử Gauss nên tính hữu dụng hơi thấp, nhưng vì tất cả các bộ giải đều cho thấy mức mở rộng theo hàm mũ, đây vẫn là một cách tốt để ước lượng hiệu năng
    Cách triển khai thú vị thứ hai liên quan đến hệ mật mã McEliece. Đây là mật mã khóa công khai từ thập niên 70, hiện đang được chú ý trở lại vì khả năng kháng lượng tử. Tấn công giải mã là bài toán tìm nghiệm của một tập phương trình XOR; bài toán này cũng ở thời gian đa thức, nhưng có thêm điều kiện rằng khoảng cách Hamming phải bằng một số nào đó nằm trong khóa công khai

  • Khi học hợp ngữ Z80 để lập trình TI-83, từng byte mã máy đều quan trọng. Lý do là toàn bộ dung lượng lưu trữ của máy tính chỉ có 24KB
    Để khởi tạo thanh ghi tích lũy chính a về 0, người ta dùng XOR a thay vì LD a, 0. Trong các lệnh toán học, a là toán hạng tự động, nên XOR a sẽ XOR a với chính nó, và toàn bộ lệnh chỉ dài 1 byte. Ngược lại, để nạp tường minh 0 vào a, literal 0 phải nằm trong opcode, nên LD a, 0 là lệnh dài 2 byte