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

191–200 of 243 posts

Re: That XOR Trick (2020)

#191

Post by gallier2 »

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 XOR trick has also the disadvantage of being 3 dependend instructions that can not overlap. The one with a temp variable has only 2 of them dependend and can therefore save one cycle on an OO CPU.

Re: That XOR Trick (2020)

#192

Post by Const-me »

Good article, but this interview question is not good.

> How to swap two numbers without using a temporary variable?

I know interviewers expect XOR, but PCs have XCHG instruction.

It’s the same error when they asking to compute number of set bits, expecting “lookup table”. Same error when they ask to find the least/most significant set bit index, expecting some bit tricks. Processors have dedicated instructions to do these things, typically faster than smart-ass manual versions.

Moreover, for simple things like XCHG, BT, BTC, BSWAP compilers are aware and normally produce them from normally-looking i.e. readable code.

Re: That XOR Trick (2020)

#193

Post by glangdale »

surajrmal wrote: post #123
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…

The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty. I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next addr…

It's not obvious how prefetching the next address would make things run that much faster - you don't know a given address until you execute the load. That said, there is definitely an extra cycle in your dependency chain to do the XOR, which you might well notice if your linked list is in cache (that extra cycle will show up).

We had a discussion on Twitter about some sort of superfast magic prefetcher that may well have been on the M1 which arguably could shave some cycles off list traversal, and there was a theory that an XOR-list would have been a good negative benchmark to prove/disprove this, but nothing came of it.

The limitation is worse than you say; you can't even navigate from an item just by knowing its address (not just remove/erase something). So any given iterator into this list has to have 2 pointers (say, the item and its predecessor).

It's a weird structure. There's probably almost certainly some peculiar use case for it somewhere, but I've never encountered such a case.

Re: That XOR Trick (2020)

#194

Post by whatshisface »

bonoboTP wrote: post #139
bidirectional wrote: post #108

Earlier quoted context omitted.

Google's policy is to extensively discuss interview questions internally, and blacklist any that are leaked. They are still complained about near-constantly on any tangentially related HN thread.

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 those topics.

Re: That XOR Trick (2020)

#195

Post by PartiallyTyped »

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

Re: That XOR Trick (2020)

#196

Post by mrmuagi »

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

Hmm, swaps the zero problem for a overflow/underflow one?

Re: That XOR Trick (2020)

#197

Post by dan-robertson »

bonzini wrote: post #28
toxik wrote: post #7

Earlier quoted context omitted.

A somewhat common use of XOR is p != q. It is actually an XOR. Another useful way to think of XOR is "either p or q is true, but not both, and not neither."

Compilers can optimize "a != b" to "a xor b" if they know that both operands are 0 or 1. There are crazy many expression rewriting rules.

They don’t need to be 0 or 1. We already know that a ^ a = 0, a ^ 0 = a, and a ^ (b ^ c) = (a ^ b) ^ c, so we must have a ^ b = 0 only when a = b. Therefore in the C convention where 0 means false, a ^ b = not (a = b) = (a!=b) (this equality only holds for expressions that are going straight into a Boolean operation (or test in eg an if statement), as a!=b should always evaluate to 0 or 1.

The compiler may use this by xoring a and b and then jumping if the zero flag was set.

Re: That XOR Trick (2020)

#198

Post by dan-robertson »

toxik wrote: post #145
globular-toast wrote: post #47

Earlier quoted context omitted.

> Another useful way to think of XOR is "either p or q is true, but not both, and not neither." That's literally what eXclusive OR means. This should be the first way to think about it.

I think most people think of XOR as “difference of bits”, which it is.

FWIW, I mostly think of it as addition in Z_2^n.

Re: That XOR Trick (2020)

#199

Post by patrec »

sleavey wrote: post #176
patrec wrote: post #101

Earlier quoted context omitted.

You are aware that ^ on a 1 bit value (like a boolean) is just !=, right?

Hah, I wrote that code on the fly and didn't check the aforementioned test implementation, where I had `(a is None) ^ (b is None)` like the other commenter suggested.

You could just write this as

    (a is None) is not (b is None)
or

    (a is None) != (b is None)
It won't make a difference (and is 1 to to 5 characters longer), but it seems "cleaner" since it's more specific.

Re: That XOR Trick (2020)

#200

Post by 3PS »

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…

To quote my old OS professor: "people who xor pointers deserve what happens to them."
Post reply on HN