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

101–110 of 141 posts

Re: That XOR Trick (2020)

#101

Post by stephencanon »

FBT wrote: post #79
OjotCewIo wrote: post #68

Earlier quoted context omitted.

> The trick works on any Abelian group ( https://en.wikipedia.org/wiki/Abelian_group -- I'll use ⋆ as the Abelian group's operation, and ~ for inversion, below.) I believe you are implying: (g(1) ⋆ ... ⋆ g(n)) ⋆ ~(g(i(1)) ⋆ g(i(2)) ⋆ ... ⋆ g(i(n-1))) = g(m) where "m" is the group element index that is not covered by "i". However, for this to work, it is requried that you can distribute the inversion ~ over the group…

> ... Does distributivity of inversion ~ over operation ⋆ follow from the other Abelian group axioms / properties? If so, how? It does. For all x and y: (1) ~x ⋆ x = 0 (definition of the inverse) (2) ~y ⋆ y = 0 (definition of the inverse) (3) (~x ⋆ x) ⋆ (~y ⋆ y) = 0 ⋆ 0 = 0 (from (1) and (2)) (4) (~x ⋆ ~y) ⋆ (x ⋆ y) = 0 (via associativity and commutativity) In (4) we see that (~x ⋆ ~y) is the inverse of (x ⋆ y). That…

Right. Another way to see this is that for a general (possibly non-Abelian) group, the inverse of xy is y⁻¹x⁻¹ (because xyy⁻¹x⁻¹ = x1x⁻¹ = xx⁻¹ = 1 [using "1" for the identity here, as is typical for general groups], or more colloquially, "the inverse operation of putting on your socks and shoes is taking off your shoes and socks"). For an Abelian group, y⁻¹x⁻¹ = x⁻¹y⁻¹, and we're done.

Re: That XOR Trick (2020)

#102

Post by zeroq »

dahcryn wrote: post #78
jonathanlydall wrote: post #63

This was a go to interview question to be solved in C# at a place I worked at a while back which had developers allocated to projects working on pretty standard line of business systems. The XOR solution was a valid answer, but not the only answer we would have happily accepted. The interview question was chosen such that it's very easy to understand and quick to solve, meaning it would indicate the candidate knew at…

you are missing the most obvious one, no? Sum both lists and take the difference, that's the missing number, since the items are guaranteed unique

overflow

Re: That XOR Trick (2020)

#103

Post by hundredwatt »

antirez wrote: post #73

About one month ago I applied XOR in a similar (but a bit more complicated way) to Redis Vector Sets implementation, in the context of sanity check of loading a vset value from the RDB file. I believe the way it works is quite interesting and kinda extends the applicability of the trick in the post. The problem is that in vector sets, the HNSW graph has the invariant that each node has bidirectional links to a set of…

A neat trick to make the accumulator both collision-resistant and self-diagnosing.

  For every normalized link id x:
      y = (x
If acc is zero, all links are reciprocal (same guarantee as before).

If acc is non-zero, split it back into (x', h'):

* Re-compute h(x').

* If it equals h', exactly one link is unpaired and x' tells you which one (or an astronomically unlikely collision). Otherwise there are >= 2 problems.

This has collision-resistance like the parent comment and adds the ability to pinpoint a single offending link without a second pass or a hash table.

Re: That XOR Trick (2020)

#104

Post by danbruc »

tomtomtom777 wrote: post #80
danbruc wrote: post #65

For calculating the XOR of 1 to n there is a closed form solution, so no need to XOR them together in a loop. (n & ((n & 1) - 1)) + ((n ^ (n >> 1)) & 1) Or a much more readable version [ n, 1, n + 1, 0 ][n % 4] which makes it clear that this function cycles through a pattern of length four. Why this works can be seen if we start with some n that is divisible by four, i.e. it has the two least significant bits clear,…

Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.

Combining two consecutive integers starting with an even one yields one.

  xxxxxxx0 ^ xxxxxxx1 = 00000001
If we start at a number divisible by four and do this twice, we get one twice.

  xxxxxx00 ^ xxxxxx01 = 00000001
  xxxxxx10 ^ xxxxxx11 = 00000001
And combining the two of course yields zero and we are right back at the start.

Re: That XOR Trick (2020)

#105

Post by noman-land »

Straw wrote: post #97

One can generalize this to k missing numbers the same way as we typically do for the addition case by using finite fields: XOR is equivalent to addition over the finite field F_2^m. So, in this field, we're calculating the sum. If we have two numbers missing, we calculate the sum and sum of squares, so we know: x + y x^2 + y^2 From which we can solve for x and y. (Note all the multiplications are Galois Field multipl…

Can you explain a bit about how and why the higher powers work?

Re: That XOR Trick (2020)

#106

Post by danbruc »

betasilly wrote: post #92
tomtomtom777 wrote: post #80

Earlier quoted context omitted.

Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.

Another interesting fact is that each time you make the xor of four consecutive numbers, beginning with an even number, the result is zero. Example in J. xor =: (16 + 2b0110) b. f =: 3 : 'xor/ y + i. 4' f"0 ] 2 * 1 + i. 100 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0…

Yes, because XORing two consecutive integers only differing in the least significant bit yields one.

  xxxxxxx0 ^ xxxxxxx1 = 00000001
Doing this twice with four consecutive numbers then also cancels the remaining one. That also means that you do not have to use consecutive numbers, you can use two arbitrary pairs

  2m ^ 2m + 1 ^ 2n ^ 2n + 1
and for example

  16 ^ 17 ^ 42 ^ 43
should be zero.

Re: That XOR Trick (2020)

#107

Post by less_less »

Straw wrote: post #97

One can generalize this to k missing numbers the same way as we typically do for the addition case by using finite fields: XOR is equivalent to addition over the finite field F_2^m. So, in this field, we're calculating the sum. If we have two numbers missing, we calculate the sum and sum of squares, so we know: x + y x^2 + y^2 From which we can solve for x and y. (Note all the multiplications are Galois Field multipl…

This will depend on the field, and for F_2^m you want odd powers: sum(x), sum(x^3), sum(x^5) etc. Using sum(x^2) won't help because squaring over F_2^m is a field homomorphism, meaning that sum(x^2) = sum(x)^2.

This is also how BCH error-correction codes work (see https://en.wikipedia.org/wiki/BCH_code): a valid BCH codeword has sum(x^i where bit x is set in the codeword) = 0 for t odd powers i=1,3,5, ... Then if some bits get flipped, you will get a "syndrome" s_i := sum(x^i where bit x was flipped) for those odd powers. Solving from the syndrome to get the indices of the flipped bits is the same problem as here.

The general decoding algorithm is a bit involved, as you can see in the Wikipedia article, but it's not horribly difficult:

  • First, extend the syndrome: it gives sum(x^i) for odd i, but you can compute the even powers s_2i = s_i^2.

  • The syndrome is a sequence of field values s_i, but we can imagine it as a "syndrome polynomial" S(z) := sum(s_i z^i).  This is only a conceptual step, not a computational one.

  • We will find a polynomial L(z) which is zero at all errors z=x and nowhere else.  This L is called a "locator" polynomial.  It turns out (can be checked with some algebra) that L(z) satisfies a "key equation" where certain terms of L(z) * S(z) are zero.  The key equation is (almost) linear: solve it with linear algebra (takes cubic time in the number of errors), or solve it faster with the Berlekamp-Massey algorithm (quadratic time instead, maybe subquadratic if you're fancy).

  • Find the roots of L(z).  There are tricks for this if its degree is low.  If the degree is high then you usually just iterate over the field.  This takes O(#errors * size of domain) time.  It can be sped up by a constant factor using Chien's search algorithm, or by a logarithmic factor using an FFT or AFFT.
You can of course use a different error-correcting code if you prefer (e.g. binary Goppa codes).

Edit: bullets are hard.

Further edit just to note: the "^" in the above text refers to powers over the finite field, not the xor operator.

Re: That XOR Trick (2020)

#108

Post by HappyPanacea »

HappyPanacea wrote: post #89
tomtomtom777 wrote: post #80

Earlier quoted context omitted.

Fascinating. It can see it work but I still can't really wrap my head around where the magic cycle length of 4 comes from.

If we generalize the problem to base k (they are k-1 duplicate of each number except the missing number, find missing one using base k-wise addition) then we can see the cycle is the smallest number such the base k-wise addition from 1 to the number is zero and it is power of k will form a cycle. I'm not sure if all such numbers are power of k if they exists or if there is an upper bound on them. For example in base…

I made an arithmetical mistake in base 4, so I was wrong. I also wrote they are instead of there are.

I think the following is true: For even k the cycle is k^2 long and for odd k is k long. Why? because units' place of generalized xor from 1 to k-1 is (k^2-k)/2 and therefore zero mod k if k is odd, if k is even then if we repeat it twice we get zero. For the second digit, k times the same digit will always give zero. Thus for odd k we have a zero when n is divisible by k and for even k we have a zero when n is divisible by 2k and the smallest power of k divisible by 2k is k^2 so it must be the cycle length.

Re: That XOR Trick (2020)

#109

Post by snozolli »

ur-whale wrote: post #57
motorest wrote: post #44

Earlier quoted context omitted.

> Ah, my least favorite technical interview question. The epitome of turning technical interviews into a trivia contest to make them feel smart. Because isn't that the point of a tech interview?

In what way is that question trivia? I believe you under-estimate what a good interviewer is trying to do with questions such as these: Either you've seen the trick before and you get an opportunity to show the interviewer that you're an honest person by telling him you have. Huge plus and the interview can move on to other topics. Either you haven't and you can demonstrate to the interviewer your analytical skills b…

It has no connection to modern software engineering. It's a clever and irrelevant trick for 99.999% of programming jobs out there.

Stop asking these asinine questions and ask questions relevant to real-world software engineering. Software engineers are their own worst enemies.

Re: That XOR Trick (2020)

#110

Post by anthomtb »

ameliaquining wrote: post #10

Ah, my least favorite technical interview question. (I've been asked it, but only after I first read about it online.)

Horses for courses.

It's silly to as ask a web dev these questions and expect these XOR approaches.

Low-level developers ("bare metal" as the kids say), on the other hand? They should have a deep enough understanding of binary representation and bitwise operations to approach these problems with logic gates.

Post reply on HN