[HN Gopher] XOR
___________________________________________________________________
XOR
Author : mariuz
Score : 153 points
Date : 2025-02-18 10:02 UTC (12 hours ago)
(HTM) web link (www.chiark.greenend.org.uk)
(TXT) w3m dump (www.chiark.greenend.org.uk)
| ipython wrote:
| Ha. TIL that if you XOR the car emoji with 0x20 (ie. you make it
| "lower case"), you get the "no pedestrian" emoji. It probably
| won't encode below but this was copied and pasted from tfa. It
| seems too coincidental to be an accident - anyone who has insight
| to know whether this was done on purpose?
|
| If you take this too far, you might get strange ideas, like the
| lower-case version of the car emoji being a 'no pedestrians'
| sign: >>> chr(ord('') ^ 32) ''
| mananaysiempre wrote:
| To satisfy HN's emoji-stripping comment mangler:
| >>> from unicodedata import lookup, name >>>
| name(chr(ord(lookup('AUTOMOBILE')) ^ 0x20)) 'NO
| PEDESTRIANS'
| rzzzt wrote:
| :tada: - :tophat:
|
| :rocket: - :mountain_cableway:
| IncreasePosts wrote:
| I would think the lowercase of a car would be a go kart
| zero_k wrote:
| But you forgot! It's also a 3-wise independent linear hashing
| function! Which means it can be used for probabilistically
| approximately uniform sampling and counting of solutions to
| boolean functions. This is super-duper useful. We use it to build
| counters that give probabilistic, but proven, counts. I explained
| the idea here in more understandable terms [1].
|
| Basically, it halves the solution space approximately correctly
| each time. So you keep on adding them, until you have say, 10
| solutions. Then you multiply the 10 with 2^k, where k is the
| number of XORs you added. That's it! So cool, no? And it's super-
| scalable, because it haves it each time, so you'll get to, say,
| 10 pretty quick!
|
| Some research papers are here [2,3]. I work on this, the tools
| are here [4,5]. In the last model counting competition, it
| dominated all other competitors, when combined with an exact
| counter, slides of the competition here [6].
|
| [1] https://www.msoos.org/2018/12/how-approximate-model-
| counting... [2] https://arxiv.org/abs/1306.5726 [3]
| https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf [4]
| https://github.com/meelgroup/approxmc [5]
| https://github.com/meelgroup/unigen [6]
| https://mccompetition.org/assets/files/2024/MC2024_awards.pd...
| niccl wrote:
| XOR is used in one of the LEET fizzbuzz answers:
| https://tech.marksblogg.com/fastest-fizz-buzz.html
| greenavocado wrote:
| Easy way to remember it: Never both together (NBT)
| lblume wrote:
| Sounds like NAND.
| polpo wrote:
| I use this to remember what it does and also like thinking of
| XOR as an operation you can apply with a mask to flip bits (the
| linked article mentions this).
| layer8 wrote:
| It's easier to remember it as a bit inverter, or as boolean
| "not equal", IMO. And "exclusive or" pretty much already spells
| out what it does.
|
| Regarding the first one I might be biased by learning XOR from
| https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/xor/#...
| , however.
| localghost3000 wrote:
| Every now and again one of these come up in a PR and I hard
| reject it every time. Its clever. Its neat. Its elegant. And it
| takes a giant ass white paper to explain it to people. Please
| please please don't use stuff like this when other people have to
| read your code.
| do_not_redeem wrote:
| Sorry but in what universe is xor too advanced for a programmer
| (someone who works with computers and numbers for a living) to
| understand? 99% of the article is just fun trivia anyway.
|
| If a deep dive like this scares you, then the + operator should
| leave you absolutely terrified, just look at the length of this
| article: https://en.wikipedia.org/wiki/Addition
| jjice wrote:
| One of my favorite XOR stories is from Bryan Cantrill (of Oxide,
| Joyent, and Sun) in this presentation [0] and this video [1].
|
| To avoid clicking a link: When he was at Sun, he was chatting
| with a coworker (Roger Faulkner) about the lack of logical XOR in
| C. Faulkner said it was because you couldn't short circuit it,
| and Brian thought that was wild. Then Roger emailed Dennis
| Ritchie to ask and he confirmed it was what Faulkner had said.
|
| That stories gets me every time! First of all, it's very funny
| and well delivered by Cantrill, but it's also just so incredible
| that they could ask the man himself.
|
| [0] https://speakerdeck.com/bcantrill/oral-tradition-in-
| software...
|
| [1] https://www.youtube.com/watch?v=4PaWFYm0kEw
| wat10000 wrote:
| C does have a logical XOR, it's the `!=` operator. Unlike other
| logical operators, it requires the arguments to be normalized
| to a single truth value. It plays nicely with C's convert-to-
| boolean operator `!!`.
| snvsn wrote:
| Topic starts at 37:18
| inasio wrote:
| A lot of custom optimization solvers (e.g. Ising Machines) these
| days benchmark on XOR problems. It's a bit useless in practice
| because solving a bunch of XOR clauses can be done in polynomial
| time with Gaussian elimination, yet the solvers all show
| exponential scaling, but it works as a good way to gauge
| performance.
|
| A second interesting implementation concederns the McEliece
| cryptocipher. It's a public key cryptocipher from the 70s that is
| enjoying a renaissance these days due to being quantum-resistant.
| The decoding attack involves finding a solution to a set of XOR
| equations (again, polynomial), but where the Hamming distance is
| equal to some number (given, part of the public key).
| an_ko wrote:
| My favourite cursed XOR trick that I think wasn't mentioned is
| XOR doubly-linked lists.
| https://en.m.wikipedia.org/wiki/XOR_linked_list
|
| Instead of each node storing the next- and previous-pointers
| separately, store a single pointer which is the XOR of the two.
| Which is obviously an invalid pointer. But when iterating, XOR
| the previous node's pointer with the combined pointer to get the
| next node's pointer, and so on. You can iterate this way in both
| directions. Feels illegal. :)
| antirez wrote:
| Among binary quantized vectors, similarity is just popcount(XOR
| of the two vectors) / num_bits. Can be linearly translated to
| cosine similarity / distance range just multiplying and
| centering.
___________________________________________________________________
(page generated 2025-02-18 23:00 UTC)