That XOR Trick | Hacker News Reader

That XOR Trick

florian.github.io

55 pointsivanvas20 comments

> XOR on the same argument: x ^ x = 0

Those who have dabbled with x86 assembly will know that this is pretty much the standard to set a register to zero. Code is peppered with the likes of 'xor eax, eax'.

Why is that though? Wouldn't something like `mov eax 0` also work?

Absolutely (well, if you add the missing comma :) ), just less efficient.

That 0 has to come from somewhere, while in the other case XORing a register with itself does not involve loading any data. It's also shorter.

It begs a question though: How many instructions in <insert ISA here> are equivalent? I assume that a compiler writer has a list of equivalents and will typically choose the shorter one?

For RISC ISAs like MIPS, then you can do a lot of

ADD Reg0 to Reg0 and store result in Rx

OR Reg0 with reg0 and store result in Rx

XOR Reg0 with reg0 and ..

The only issue is that for RISC, all these instructions are of equal length, so flipping them around would gain you very little, or more likely zero effect unless you are chasing some corner case thing like "XOR instruction value compresses slightly better than ADD because.."

There are a number of considerations there. Size is only one of them. Speed and internal processor state effects are two others. For instance, a larger, slower instruction might prevent a pipeline stall in a particular function or might enable loop unrolling or might allow a shorter loop unrolling, while in a similar function that doesn’t pipeline the same way, the compiler will choose a faster instruction.

You're right I completely overlooked pipelining. I guess I'm out of my depth here

Well that 0 that you are loading comes from the instruction, so it is already "there". It boils down to the fact that the instruction is sorter.

In fact in theory the load is slower, because XOR has data dependencies on the arguments. So an out-of-order processor could be delayed. However x86 has special logic that XOR with itself doesn't carry any dependencies on the arguments.

In addition to other concerns, processors usually treat xor specially since it was the best way to zero things for so long that it became ubiquitous. Often its performance impacts are equivalent to a noop.

My favorite application is comparing vectors. Example in C++:

    // Compare 32 bytes for equality, with 2 AVX2 instructions
    inline bool equals( __m256i a, __m256i b )
    {
        // When the vectors are equal, their XOR is completely zero..
        __m256i xx = _mm256_xor_si256( a, b );
        // ..and there's a special instruction to test the complete vector for zero
        return (bool)_mm256_testz_si256( xx, xx );
    }

The “missing integer” example is awkward, because what’s interesting here is not whether you can solve the problem with xor or plus, but whether you need two loops or just one. Edit: I guess overflow is one consideration, as mentioned in the article.

See also, "Hacker's Delight" by Henry Warren for a deep dive into bit manipulation tricks.

It took me a minute to figure out the last step of the final example since the author doesn’t quite spell it out. So for anyone else who’s feeling a little slow:

Once you’ve partitioned the search space into “values where the ith bit is 0” and “values where the ith bit is 1” (for example, even and odd values if it happens to be the least significant bit), then you can simply iterate through all the input values and xor together all the values where the ith bit is 0, then xor those with all possible values where the ith bit is 0, and you’ve found one of the missing values. Repeat the process with 1 instead of 0 to find the other.

Nitpick: I think the trick(s) also depend on XOR being associative.

Are there any more complex applications of this, especially if you generalize it to any operator that obeys the necessary properties? I'm curious if there's any sort of interesting data structures you can build, probably building on commutative monoids where x `mappend` x == mempty for all x (the generalization of x^x == 0).

> Application 1: In-Place Swapping

Warning: if x == y, then instead of swapping, the two values are set to zero.

So this swapping trick works only for x!=y.

---------

The other tricks are interesting, and likely hold the key to some kind of parallel programming trick, as a sequence of XORs is trivially parallelizable through the prefix-sum pattern.

All of the other tricks are O(n) number of XOR operations, while parallel prefix-sum is O(log(n)) depth and O(n) total work.

>Warning: if x == y, then instead of swapping, the two values are set to zero.

Huh, what?

You're right. Sorry, my bad. I misremembered the actual issue.

The issue is:

    void xor_swap(int& x, int& y){
        x ^= y;
        y ^= x;
        x ^= y;
    }

The issue is *aliasing*. If the pointer &x == &y, then everything goes to crap. When the pointers alias to themselves, the function degenerates into:

        x ^= x;
        x ^= x;
        x ^= x;

Which sets x (and the y value) to zero.

In contrast:

    void regular_swap(int& x, int& y){
        int tmp = x; 
        x = y;
        y = tmp;
    }

This always works, even with aliasing.

This one-liner works for x==y: x ^= y ^ (y = x); Is this really code, or some kind of new text emojis? :)

x ^= y ^ (y = x); //one-liner

Went to bookmark this not realising I had already bookmarked it!

Reply on news.ycombinator.com