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

221–230 of 243 posts

Re: That XOR Trick (2020)

#221

Post by [deleted] »

user-the-name wrote: post #129
surajrmal wrote: post #123

Earlier quoted context omitted.

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…

Also, I think this may be the only data structure I have heard of that has an O(1) reverse ordering operation?

[deleted]

Re: That XOR Trick (2020)

#222

Post by ganafagol »

mrmuagi wrote: post #196
PartiallyTyped wrote: post #195

Earlier quoted context omitted.

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?

Worse. The zero problem does not exist if the two variables are at different memory locations. The overflow problem of this solution always exists. Plus, if a and b are at the same memory location, it suffers from the same zero problem.

Re: That XOR Trick (2020)

#223

Post by randomswede »

globular-toast wrote: post #209
dan-robertson wrote: post #198

Earlier quoted context omitted.

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

That is more traditional. It's addition without carry.

Although in Z_2^n, "addition without carry" and "subtraction without carry" are the same operation.

Re: That XOR Trick (2020)

#224

Post by randomswede »

smlckz wrote: post #94
abalaji wrote: post #89

Earlier quoted context omitted.

right but OP’s solution for this part of the problem is assumed to be instantaneous (ie O(0))

What is O(0)? Computation that takes 0 time? Does that make any sense?

It is the class of functions that have the constant value 0, with a canonical exemplar f(n) = 0 (and despite having tried, I cannot find any other function, up to choice of variable name).

In terms of algorithms, I suspect that no actual algorithm fits into it and as such it is more a curiosity than actually useful.

However, O(0) is not the same as O(1), as we cannot find a constant c such that 0c dominates all possible functions that 1c can dominate.

Re: That XOR Trick (2020)

#225

Post by Kwpolska »

nickelpro wrote: post #19
danpalmer wrote: post #4

As mentioned in this article, x ^ x == 0. Fun fact, this is frequently used by compilers as a "cheap" way to zero out a register. In addition, there are comparatively few cases in programming where we XOR. Sure, it happens in things like games quite a lot, but the main use is actually _cryptography_. Between these two facts (more like hints really), I managed to reverse engineer the bulk of a piece of malware I was g…

Xor'ing registers isn't a compiler trick or arcane piece of lore, it's the canonical way to zero a register on most architectures. It's the only universally recommended way for both Intel and AMD x86 and x64 processors.

You make it sound as if there were four Intel/AMD x86/x64 architectures. And well, there aren’t. The vendor split is not a thing, we’re all running the same software on Intel and AMD x86/x64 processors. And you could argue that the x86/x64 split doesn’t really matter for this, since x64 is a superset of x86 and inherits this tradition from the 16-bit and 32-bit eras.

Re: That XOR Trick (2020)

#226

Post by ChrisRR »

voldacar wrote: post #217
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

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

As with every performance optimisation, it's better to test and profile rather than to assume

Re: That XOR Trick (2020)

#227

Post by ChrisRR »

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);

I know normally python is simpler and easier to read, but this is not one of those times.

The example C++ is much easier to read and more intuitive as to what it does.

Re: That XOR Trick (2020)

#228

Post by Fazel94 »

> Arithmetic operators instead of XOR In that case, It uses Python that supports arbitrary long numbers out of the box so overflow of integers wouldn't be an issue(in Python3 default is arbitrary long integers).

Re: That XOR Trick (2020)

#229

Post by mhh__ »

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…

On top of that, the CPU can literally elide movs at runtime so the whole swap could end up being zero latency depending on the code motion

Re: That XOR Trick (2020)

#230

Post by mhh__ »

gallier2 wrote: post #191
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.

Even in a old OOO core because of register renaming and friends the swap could have a latency of zero in the first place.
Post reply on HN