XOR

Original Article ↗ Hacker News Discussion ↗

Emoji coincidences and intuition pumps

  • Commenters note fun Unicode coincidences: XOR-ing the car emoji with 0x20 gives “no pedestrians”, and other emoji pairs map similarly when “case-flipped.”
  • People share ways to remember XOR: “never both together,” “bit inverter,” “not equal,” stairway light switches, “red pill vs blue pill,” and “hetero operator.”
  • A puzzle about filling an N×N array with the smallest unused integer (left/above) is hinted to have an XOR-based pattern.

Practical and advanced uses of XOR

  • Highlight of the thread: XOR as a 3‑wise independent linear hash for approximate model counting and near-uniform sampling of SAT solutions. By adding random XOR constraints that roughly halve the solution space, you can estimate counts as 2^k times the remaining solutions.
  • Other applications mentioned:
    • FizzBuzz “leet” implementations.
    • Binary vector similarity via popcount(XOR).
    • Kademlia DHT’s distance metric (XOR on node IDs) and its nice “symmetric neighborhoods” compared to other DHTs.
    • XOR-based constraints in optimization / Ising machines and in McEliece cryptosystem decoding.

Low-level tricks, graphics, and nostalgia

  • Classic XOR tricks: XOR-linked lists (prev⊕next pointer), XOR-based zeroing of registers on 8‑bit CPUs, and virus “encryption”/obfuscation.
  • GUI/graphics: XOR drawing for rubber-band rectangles, both to erase/revert and to keep outlines visible over filled regions. A patent on XOR drawing reportedly contributed to legal trouble for a major 80s/90s vendor.
  • XOR swap is revisited: people note it’s error-prone (fails if both pointers alias the same location) and unnecessary on modern hardware.

Readability and “cleverness” vs fundamentals

  • One camp rejects XOR tricks in production code as “too clever” and hard to understand, preferring explicit, readable swaps and structures.
  • Others counter that XOR is basic boolean logic; if colleagues can’t read it, that’s a deeper skills issue. But there’s agreement that micro-optimizing with XOR swap or excessive bitmaps usually isn’t worth the complexity.

Logic, C semantics, and terminology

  • Discussion around C’s lack of a dedicated logical XOR (short‑circuitable) versus bitwise ^, and using != / !a != !b as logical XOR.
  • A detailed subthread distinguishes two notions:
    • Parity (sum mod 2 over many bits / operands).
    • “Exclusive or” in natural language and math (“exactly one” true), noting that they only coincide for two inputs and that programmers often conflate them.