Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

That XOR Trick (2020)

florian.github.io

Post reply on HN
Print view View original

211–220 of 243 posts

Re: That XOR Trick (2020)

#211

Post by bonoboTP »

whatshisface wrote: post #194
bonoboTP wrote: post #139

Earlier quoted context omitted.

The attitude is often quite strange. Like on Twitter I saw a few days ago that many were riled up about the fact that a prof would ask how to solve Ax=b (linear algebra) for a deep learning / computer vision PhD position. People were calling this unnecessary gatekeeping ... I'm like that's just a warm-up question to get comfortable... But apparently the loud online hive mind opinion is that all that should count is s…

To be fair, you would not actually need to know how numpy.linalg.solve works to use pytorch. Solving linear equations is an extremely deep subject on its own, featuring a lot of difficult and sophisticated issues related to numeric stability. Entire books have been written about how to solve Ax=b with awareness of the nature of floating point arithmetic. Machine learning researchers are generally unconcerned with tho…

As everything in the world of knowledge, this topic too has a fractal nature. There's a difference between what you just said vs "well, optimize it with gradient descent, yoloswag" or "just invert the matrix A". If you say something something pivot selection, Gauss elimination, iterative algorithms, QR, LU factorization, backslash operator, pseudoinverse, under and overdetermined systems and can roughly handwave your way around roughly explaining what these things are about, it's probably already very good for this job. This prof probably wasn't interested in the tiniest of numerical stability details.

Re: That XOR Trick (2020)

#212

Post by woofie11 »

whimsicalism wrote: post #75
woofie11 wrote: post #59

Earlier quoted context omitted.

I think it kind of depends on the type of programmer one wants to hire. There are different roles, solving different types of problems. There are places for people with technical brilliance, there are places for people with social brilliance, with both, and with neither. That's healthy. You want a diverse economy with different types of positions for different types of folks, and vice-versa. If I ask a half-dozen que…

> there are places for people with social brilliance, with both, and with neither. That's healthy There are lots of socially brilliant people out there, it's what many of us spend at least 20 years of our lives practicing. Why would being a brilliant socializer command the same salary that a brilliant engineer does?

Because, as you move up the management chain, understanding how people work and how groups of people work becomes more important than technical brilliance. The job of a manager is to create a healthy working environment where people work effectively, and are well-aligned to a common goal.

That's hard.

You don't just practice that by living.

That's made easier by having people lower down who are helping and not hurting.

Re: That XOR Trick (2020)

#213

Post by Iwan-Zotow »

tobinfricke wrote: post #169
simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

People like to harp on C++, but templates permit code that is simultaneously maximally clear and efficient: #include swap(s[i], s[j]);

Prefer pythonic style

std::tie(b, a) = std::make_tuple(a, b);

Re: That XOR Trick (2020)

#214

Post by WalterBright »

simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

> how to find a duplicate in an integer list by using xor

I've never heard of that trick and would never have thought of it on my own. It takes a moment's thought to see why it works, and I like it.

Bit twiddling is a bit like symbolic integration. There isn't a systematic approach, it's just an accumulation of formulae that people have stumbled upon over time. You can buy books of them. (These days, of course, you just use a program that has them all hardcoded into it.)

Re: That XOR Trick (2020)

#215

Post by m463 »

simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

that's a very sharp edge case.

Re: That XOR Trick (2020)

#216

Post by drallison »

FabHK wrote: post #150
hyperman1 wrote: post #63

A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next} The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;} While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also wo…

It's been used in the real world, on the Cambridge Z88, ca. 1987: https://www.cl.cam.ac.uk/~jrh13/devnotes/all.html#sec218 This XOR-list trick was mentioned by Joel Spolsky in "The Duct Tape Programmer" (2009), discussed recently here. > They have to be good enough programmers to ship code, and we’ll forgive them if they never write a unit test, or if they xor the “next” and “prev” pointers of their linked list into…

Single pointer lists using the XOR trick were used, I believe, to implement the XDS Sigma 7 operating system block free list back in the day when memory was not free and core dumps were the primary debug tool. I remember writing a column on the algorithm for Dr. Dobbs Journal back in the 1980s. There are lots of bit twiddling techniques that use XOR. Henry Warren's Hackers Delight is a good reference there. And, of course, Don Knuth's AOCP has lots of information. Volume 4A, available as a fascicle, has a number of XOR algorithms.

Re: That XOR Trick (2020)

#217

Post by voldacar »

azhenley wrote: post #100
simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

The code from the Wikipedia article for XOR swapping [1] checks if the values are equal. void XorSwap(int *x, int *y) { if (x != y) { *x ^= *y; *y ^= *x; *x ^= *y; } } [1] https://en.wikipedia.org/wiki/XOR_swap_algorithm

Wouldnt the extra branch kill any performance improvement you were getting from the xor trick?

Re: That XOR Trick (2020)

#218

Post by CamperBob2 »

Iwan-Zotow wrote: post #213
tobinfricke wrote: post #169

Earlier quoted context omitted.

People like to harp on C++, but templates permit code that is simultaneously maximally clear and efficient: #include swap(s[i], s[j]);

Prefer pythonic style std::tie(b, a) = std::make_tuple(a, b);

Why? That's about 400% harder to read. Even someone who doesn't know how to program in any language can probably infer what the C++ example does.

Re: That XOR Trick (2020)

#219

Post by Izkata »

PartiallyTyped wrote: post #195
simias wrote: post #46

Careful abusing these tricks. Over 10 years ago I decided to implement an RC4 (arcfour) cypher to generate pseudorandom noise for a test program. The algorithm looks like (from wikipedia): i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap values of S[i] and S[j] K := S[(S[i] + S[j]) mod 256] output K endwhile Being a smartass 1337 coder (and declaring intermediate variables alway…

I have an alternative to the xor trick that doesn't suffer from zeros. def swap(a,b): a=a-b b=a+b a=b-a return a,b

Uh,

  def swap(a, b):
      return b, a
?

Or since this is presumably python, just inline it without a function:

  (a, b) = (b, a)

Re: That XOR Trick (2020)

#220

Post by seanwilson »

I've used XOR for undo/redo when I had limited memory in a painting app:

- You have the canvas in state S before you draw on it and the canvas in state T after you draw on it.

- Store (S XOR T). XOR this against T to undo back to S and XOR again to redo back to T.

So if you want to have 10 levels of undo, you only need to store the final state and the 10 XOR diffs that got you there. The diffs will compress well too because most of the pixels on them will be blank (where nothing changed).

All fairly easy to implement too e.g. compared to storing and replaying high-level commands to redo.

Post reply on HN