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

141–150 of 243 posts

Re: That XOR Trick (2020)

#141

Post by jfk13 »

simias wrote: post #136
ufo wrote: post #74

Earlier quoted context omitted.

On the topic of intermediate variables, when I'm forced to use c89 I'm really shameless about introducing extra code blocks in the middle of other blocks. For example, {int i; for(i=0; i Still bothersome but better than having to declare everything at the top of the function, IMO.

I agree, but I think back then I didn't know this trick. I also abuse blocks in Rust, but it's more in order to placate the borrow checker...

That's not necessarily abuse; it may be quite appropriate to explicitly limit something's lifetime.

Re: That XOR Trick (2020)

#142

Post by svorcmar »

whimsicalism wrote: post #90
webel0 wrote: post #81

Earlier quoted context omitted.

One of several. But I agree with the general sentiment.

It just surprises me that they aren't rotated out more frequently (annually?). I can think of a number of arguments for doing so and really only one small one against.

Could you share some of the arguments you have in mind?

Re: That XOR Trick (2020)

#143

Post by Someone »

wongarsu wrote: post #116
azhenley wrote: post #100

Earlier quoted context omitted.

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

At that point it's probably almost always better to just use some temporary space, rather than dealing with all the overhead of a branch (what if it's mispredicted, what about the resources in the branch predictor tied up by this that might cause something else to be mispredicted). On the other hand there are many situations where you can guarantee that x and y are not the same space in memory (for example because th…

If they’re local variables, the compiler may not need to generate any code for a swap. It could do the equivalent of register renaming (https://en.wikipedia.org/wiki/Register_renaming)

Re: That XOR Trick (2020)

#144

Post by FabHK »

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

> checks if the values are equal

Not the values (the values being equal doesn't break the trick), but the pointers. That is, if you use the XOR trick to swap a value with itself, then it will be set to zero, instead.

As if you had written:

  x ^= x
  x ^= x
  x ^= x
Yeah, now x would be zero, not itself.

Re: That XOR Trick (2020)

#145

Post by toxik »

globular-toast wrote: post #47
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."

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

Re: That XOR Trick (2020)

#146

Post by gnull »

greggman3 wrote: post #138

I've been asked this question before. I don't remember if I already knew the answer or not. But.... When does this ever come up in the real world. > You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. This has happened to me in real life exactly NEVER! I think maybe I was asked you have a list…

> This has happened to me in real life exactly NEVER!

Do you do something applied like programming? I think problems (and solutions) similar to this one should be easy to find in TCS.

The problem you quote seems valuable to me for its insight, it shows that you can reduce certain search problems to algebraic calculations which are easy to do. I think this is useful concept to understand, and a good mental exercise to try coming up with it yourself (even if you don't apply it directly).

Could it be that even if you're a programmer who will never have to solve exactly this problem, you could still use the intuition you gain from this problem to solve others (or understand existing solutions you need to implement)? Could it be that you indirectly used the knowledge you have of this solution without being aware of it?

Re: That XOR Trick (2020)

#147

Post by [deleted] »

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

[deleted]

Re: That XOR Trick (2020)

#148

Post by usefulcat »

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…

> And that's the story of how I never used this trick ever again.

I agree with your point, and I would go on to say that this is an excellent example of the value of tests. Especially with something so relatively small and self-contained, which makes it easy to test.

Re: That XOR Trick (2020)

#149

Post by physicles »

greggman3 wrote: post #138

I've been asked this question before. I don't remember if I already knew the answer or not. But.... When does this ever come up in the real world. > You are given an array of n - 1 integers which are in the range between 1 and n. All numbers appear exactly once, except one number, which is missing. Find this missing number. This has happened to me in real life exactly NEVER! I think maybe I was asked you have a list…

I had a case today where I was comparing two sets for equality. If the range of values is large, you could xor everything together as a O(1) space check for likely equality. Result is nonzero -> sets definitely aren’t equal; result is zero -> sets are probably equal, but you’ll need to check again some other way to make sure.

Of course this is absurd if you’re dealing with anything that already fits in ram, but it’s still neat to think about.

Re: That XOR Trick (2020)

#150

Post by FabHK »

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 a single DWORD to save 32 bits, because they’re pretty enough, and smart enough, to pull it off.

https://news.ycombinator.com/item?id=25715414

and this comment pointed out the real world usage:

https://news.ycombinator.com/item?id=25718147

Post reply on HN