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

201–210 of 243 posts

Re: That XOR Trick (2020)

#201

Post by deathanatos »

whimsicalism wrote: post #71
airstrike wrote: post #62

Earlier quoted context omitted.

> You have a single question that is your "initial code screen"? He never claimed that. It could just be part of the screen

You're right and my question was poorly phrased. I meant: you have a single question that is asked as part of every single screen every year?

I'm not sure what you mean by "every year", but when I screen candidates, yes, I'll ask multiple candidates the same question? It allows me to compare candidates directly without introducing the additional variable of wondering whether one had a harder question, it allows me to gain & retain experience at asking the question in how it is presented, and if the candidate does well, how we proceed to make it more difficult to suss out the candidate's skill.

I do agree with the parent above though that this use of xor is trivia, and not a great interview question.

Re: That XOR Trick (2020)

#202

Post by simias »

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

That suffers from the same problem if a and b are pointers to the same thing (which was the issue in my code, since I indexed the same cell of the array).

Note that the problem is not that a and b have the same value, or even that one of them is 0, it's that a and b alias to the same memory location, effectively being two handles to the same variable.

Re: That XOR Trick (2020)

#203

Post by logbiscuitswave »

I’m a programmer by trade (and I like to think I’m pretty competent), but self-trained. Algorithms have always been a weakness of mine as a result of a lack of formal training.

While I use XOR for some simple Boolean comparisons out of convenience, the kind of XOR use I see —- especially in crypto libraries has always been very mysterious to me. This article cleared up a lot of that for me.

That being said, I often prefer readability over fancy so I don’t imagine using these tricks regularly but it’s nice to better understand how they work. This article did a great job demistifying this practice.

Re: That XOR Trick (2020)

#204

Post by Taniwha »

Snild wrote: post #153
wongarsu wrote: post #116

Earlier quoted context omitted.

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…

The xor swap truck is rarely better. It causes pipeline stalls, and so is likely to be significantly slower than the trivial swap. The temporary storage will be in a register, so it's (usually) not causing memory accesses.

Yeah exactly this, it only really makes sense in some very limited situations in embedded software, for example when you might be in an interior handler and have no free registers

Re: That XOR Trick (2020)

#205

Post by blt »

On a less clever note, I also find it useful to think about XOR as the "conditional inversion" operator:

    x  invert?  out
    0  0        0
    1  0        1
    0  1        1
    1  1        0
This has saved me some nested if-statements before.

Re: That XOR Trick (2020)

#206

Post by dandanua »

Straw wrote: post #131
dandanua wrote: post #110

Earlier quoted context omitted.

Addition in F_{2^k} is not the same as XORing. But that summation idea is correct. To solve polynomial you can use this algorithm https://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algo...

Oh, neat, what's the runtime? https://math.stackexchange.com/questions/1479745/relations-o... What have we missed?

Ah, XORing is indeed addition in F_{2^k}. It's not addition in Z_{2^k}, though. I was thinking about summation modulo prime number, in this case Z_p = F_p.

Re: That XOR Trick (2020)

#208

Post by ufo »

ignoramous wrote: post #70

One of the coolest XOR tricks I've seen is fast encoding of negative integers to positive integers (unsigned) employed by ProtoBufs. It is called ZigZag encoding where negative and positive integers are interleaved such that lower negative values are assigned to lower positive values: input zz(int) 0 0 1 2 2 4 3 6 -1 1 -2 3 zz(n int64) => (n > 63) unzz(n int64) => (n >> 1) ^ (-(n & 0x1)) https://developers.google.com…

Doesn't a bitwise OR work just as well as a XOR here?

Re: That XOR Trick (2020)

#210

Post by contravariant »

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?

If you stick to multiplication and addition then the beauty of modular arithmetic ensures that over and underflow are only a problem if your final result under/overflows.

In particular you can solve the problem in this article by just subtracting the numbers from 1+2+...+n-1+n. The remainder will be your missing number (though be careful with the 1+2+...+n-1+n = n(n-1)/2 formula; division by 2 is very much not compatible with arithmetic modulo a power of 2, so divide first then multiply, or keep a running total if you want to be flexible).

Post reply on HN