That XOR Trick (2020) • Hacker News Board

Re: That XOR Trick (2020)

#11

Post by IgorPartola » Mon, Jan 18, 2021, 2:38 PM UTC

So this is how you’d solve the Fallout 3+ hacking challenges? :)

In practice I cannot think of a time when I was confronted with this particular problem. Usually if I need to find a duplicate I have no guarantees that there isn’t more than one or if there is a duplicate at all. I don’t think I’ve ever had to practically solve the “every number but one” problem. Curious where such problems arise in the wild, except interview puzzles.

Re: That XOR Trick (2020)

#12

Post by blauditore » Mon, Jan 18, 2021, 2:39 PM UTC

This is conceptually almost the same as summing over all entries and comparing to the sum of all numbers in [1, n], except that the latter can be done more efficiently because that sum is simply n*(n+1)/2.

There are in fact legit use cases for XOR to speed things up or make algorithms simpler, but this is not the case here IMHO.

Re: That XOR Trick (2020)

#13

Post by IgorPartola » Mon, Jan 18, 2021, 2:40 PM UTC

diegocg wrote: post #8

The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.

So you do a check beforehand for whether you need to swap them at all?

Re: That XOR Trick (2020)

#14

Post by flohofwoe » Mon, Jan 18, 2021, 2:40 PM UTC

diegocg wrote: post #8

The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.

It also works if both are equal since only one value will ever be zero:

x=2, y=2:

x^=y => x=0, y=2

y^=x => x=0, y=2

x^=y => x=2, y=2

Re: That XOR Trick (2020)

#15

Post by wagslane » Mon, Jan 18, 2021, 2:40 PM UTC

I recently wrote an article explaining what makes XOR so special - may help put this in context: https://qvault.io/2020/01/18/why-is-exclusive-or-xor-importa...

Re: That XOR Trick (2020)

#16

Post by trinovantes » Mon, Jan 18, 2021, 2:42 PM UTC

Xor trick may reduce the time/space complexity of a solution but I'd say it definitely increases the cognitive load (maintenance) complexity. Outside of few niche industries/use cases, the increased developer cost will probably outweigh whatever extra hardware you'd need to compensate.

Re: That XOR Trick (2020)

#17

Post by lifthrasiir » Mon, Jan 18, 2021, 2:42 PM UTC

tlb wrote: post #3

> XOR all values between 1 and n An O(n) algorithm!? You'd expect there to be a closed-form solution for this, analogous to summing a series using n*(n-1)/2. OEIS to the rescue. http://oeis.org/A077140 gives ((n+1)%2)*n + (n+(n%2))//2 % 2

It was not super obvious to me, but the actual sequence is https://oeis.org/A003815 which is the absolute value of A077140. The entry for the latter gives another formula for A003815 however, which is distinct from a formula (1+3x-x^2+x^3)*x/(1-x^4)/(1-x^2) given in A003815.

Re: That XOR Trick (2020)

#18

Post by extropy » Mon, Jan 18, 2021, 2:43 PM UTC

diegocg wrote: post #8

The xor swap can be dangerous: if variables have the same value, they xor to zero so you end up losing the values of both variables.

a = 5 b = 5 a = a ^ b = 0 b = a ^ b = 5 a = a ^ b = 5

You where saying?

Re: That XOR Trick (2020)

#19

Post by nickelpro » Mon, Jan 18, 2021, 2:43 PM UTC

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.

Re: That XOR Trick (2020)

#20

Post by FartyMcFarter » Mon, Jan 18, 2021, 2:44 PM UTC

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…

Hashing is another big use case.

For example, XOR is the most convenient combining function for Zobrist hashes in chess programs. OR/AND would be bad choices: given random input, their output is biased to the values 1 and 0 (respectively).