【Hacker News搬运】XOR

[hackernews]

Title: XOR

XOR

Text:

hn link

Url: https://www.chiark.greenend.org.uk/~sgtatham/quasiblog/xor/

很抱歉，但作为一个文本处理模型，我无法直接访问互联网或外部链接来获取内容。因此，我无法访问您提供的链接或使用JinaReader或其他工具来分析该链接的内容。

不过，如果您能够提供该链接的内容或者其摘要，我可以帮助您分析并总结这些信息。如果您需要将非中文内容翻译成中文，请提供文本内容，我可以使用我的语言处理能力来协助翻译。

Post by: mariuz

Comments:

an_ko: My favourite cursed XOR trick that I think wasn't mentioned is XOR doubly-linked lists. <a href="https://en.m.wikipedia.org/wiki/XOR_linked_list" rel="nofollow">https://en.m.wikipedia.org/wiki/XOR_linked_list</a><p>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.

an_ko: 我最喜欢的诅咒XOR技巧，我认为不是；t提到的是XOR双链表<a href=“https://en.m.wikipedia.org:XOR_linked_list”rel=“nofollow”>https://&#x2F；en.m.wikipedia.org；维基；XOR_linked_list</a><p>不是每个节点分别存储下一个和前一个指针，而是存储一个指针作为两者的XOR。这显然是一个无效的指针。但是在迭代时，XOR前一个节点；s指针与组合指针以获得下一个节点；s指针等等。您可以在两个方向上迭代。感觉不合法：）

zero_k: 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].<p>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!<p>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].<p>[1] <a href="https://www.msoos.org/2018/12/how-approximate-model-counting-works/" rel="nofollow">https://www.msoos.org/2018/12/how-approximate-model-counting...</a>
[2] <a href="https://arxiv.org/abs/1306.5726" rel="nofollow">https://arxiv.org/abs/1306.5726</a>
[3] <a href="https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf" rel="nofollow">https://www.cs.toronto.edu/~meel/Papers/cav20-sgm.pdf</a>
[4] <a href="https://github.com/meelgroup/approxmc">https://github.com/meelgroup/approxmc</a>
[5] <a href="https://github.com/meelgroup/unigen">https://github.com/meelgroup/unigen</a>
[6] <a href="https://mccompetition.org/assets/files/2024/MC2024_awards.pdf" rel="nofollow">https://mccompetition.org/assets/files/2024/MC2024_awards.pd...</a>

zero_k: 但你忘了！它；s也是一个3维独立线性散列函数！这意味着它可以用于布尔函数解的概率近似均匀采样和计数。这是超级有用的。我们用它来构建计数器，给出概率性但经过验证的计数。我在这里用更容易理解的术语解释了这个想法[1]<p> 基本上，每次它都会大致正确地将解空间减半。所以你继续添加它们，直到你有10个解决方案。然后将10乘以2^k，其中k是相加的XOR数。那；就是这样！这么酷，不是吗？而且它；它具有超强的可扩展性，因为它每次都有，所以您；我会很快达到10分<p> 一些研究论文在这里[2,3]。我致力于此，工具就在这里[4,5]。在上一次模型计数比赛中，当与一个精确的计数器结合时，它在这里的比赛中占据了所有其他竞争对手的优势[6]<p> [1]<a href=“https:&#x2F；www.msoos.org&#x2F:2018&#x2F/12&#x2F-近似模型计数是如何工作的�”rel=“nofollow”>https:&#x2F；www.msoos.org；2018年；12℉；如何近似模型计数</一[2] <a href=“https://arxiv.org/abs-1306.5726”rel=“nofollow”>https://&#x2F；arxiv.org；abs；1306.5726</a>[3] <a href=“https://www.cs.toronto.edu~meel-Papers-cav20-sgm.pdf”rel=“nofollow”>https:&#x2F；www.cs.toronto.edu~meel；论文&quot；cav20-sgm.pdf</a>[4] <a href=“https:&#x2F；/ github.com&#x2F-meelgroup&#x2F/approxic”>https:&quot&#x2F；github.com；meelgroup；近似</a>[5] <a href=“https:&#x2F；/ github.com&#x2F-meelgroup&#x2F/unigen”>https:&quot&#x2F；github.com；meelgroup；unigen</a>[6] <a href=“https:&#x2F；mccompetition.org&#x2G；assets&#x2024；MC2024_awards.pdf”rel=“nofollow”>https:&#x2F；mccompetition.org；资产；文件&#x2F；2024年；MC2024_病房</a>

jjice: One of my favorite XOR stories is from Bryan Cantrill (of Oxide, Joyent, and Sun) in this presentation [0] and this video [1].<p>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.<p>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.<p>[0] <a href="https://speakerdeck.com/bcantrill/oral-tradition-in-software-engineering-passing-the-craft-across-generations?slide=17" rel="nofollow">https://speakerdeck.com/bcantrill/oral-tradition-in-software...</a><p>[1] <a href="https://www.youtube.com/watch?v=4PaWFYm0kEw" rel="nofollow">https://www.youtube.com/watch?v=4PaWFYm0kEw</a>

jjice: 我最喜欢的XOR故事之一是布莱恩·坎特里尔（来自Oxide、Joyent和Sun）在本次演示文稿[0]和本视频[1]中的故事<p> 为了避免点击链接：当他在Sun时，他正在与一位同事（罗杰·福克纳）谈论C.中缺乏逻辑XOR。福克纳说这是因为你不能；不要把它短路，布莱恩觉得这太疯狂了。然后罗杰给丹尼斯·里奇发邮件询问，他证实福克纳就是这么说的<p> 这些故事每次都让我着迷！首先，它；Cantrill的表演很有趣，也很好，但它；他们甚至可以亲自问这个人，这太不可思议了<p> [0]<a href=“https:&#x2F；speakerdeck.com&#bcantrill&#x2O；软件工程中的口头传统将技艺代代相传？slide=17”rel=“nofollow”>https:&#x2F；speakerdec.com；bcanthill&#x2F；软件口头传统</a> <p>[1]<a href=“https:”www.youtube.com“watch？v=4PaWFYm0kEw”rel=“nofollow”>https:”&#x2F；www.youtube.com；看？v=4PaWFYm0kEw</a>

OuterVale: If anyone is wondering, this is the same Simon Tatham as in Simon Tatham's Portable Puzzle Collection. If you're unfamiliar and ever find yourself offline and bored, they're worth checking out.<p>I know I burnt many hours in high school playing them.<p><a href="https://www.chiark.greenend.org.uk/~sgtatham/puzzles/" rel="nofollow">https://www.chiark.greenend.org.uk/~sgtatham/puzzles/</a>

OuterVale: 如果有人想知道，这就是Simon Tatham中的Simon Tatham；s便携式拼图集。如果您；他们不熟悉，总是发现自己离线和无聊，他们；值得一看<p> 我知道我在高中玩这些游戏浪费了很多时间<p> <a href=“https://www.chiark.greended.org.uk~sgtatham&#x2F；谜题/”rel=“nofollow”>https://&#x2F；www.chiark.greenand.org.uk~sgtatham；谜题</一

ipython: 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?<p>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:<p><pre><code> >>> chr(ord('') ^ 32)
''</code></pre>

ipython: 哈。TIL，如果你将汽车表情符号与0x20进行异或（即，你将其设为“小写”），你将得到“小写”；禁止行人&quot；表情符号它可能赢了；下面没有编码，但这是从tfa复制粘贴的。这似乎太巧合了，不可能是意外——有人知道这是不是故意的吗<p> 如果你做得太过分，你可能会有奇怪的想法，比如汽车表情符号的小写版本是“禁止行人”标志：<p><pre><code>&gt&&gt；&gt；chr（ord（■）^32）&#x27&#x27</代码></pre>