That XOR Trick (2020) • Hacker News Board

Re: That XOR Trick (2020)

#131

Post by nullc » Thu, Jul 03, 2025, 11:26 PM UTC

less_less wrote: post #107

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 so…

Yesterday I linked to an implementation (with complexity quadratic in the number of errors) I helped to create in another comment in this thread.

> constant factor using Chien's search algorithm

Chien's search is only really reasonable for small field sizes... which I think doesn't really make sense in this application, where the list is long and the missing elements are relatively few.

Fortunately in characteristic 2 it's quite straight forward and fast to just factor the polynomial using the berlekamp trace algorithm.

Re: That XOR Trick (2020)

#133

Post by canyp » Fri, Jul 04, 2025, 1:26 AM UTC

The more interesting xor trick beyond interview trivia is the xor list:

https://en.wikipedia.org/wiki/XOR_linked_list

Re: That XOR Trick (2020)

#134

Post by Thorrez » Fri, Jul 04, 2025, 4:07 AM UTC

danbruc wrote: post #87

Thorrez wrote: post #76

Earlier quoted context omitted.

In your array-based equation, you say n+1, but in your explanation you say n+3. Is that a mistake?

No, that is correct, those two n represent slightly different things. n + 3 is the value after n XOR n + 1 XOR n + 2, so the n in the array index expression is n + 2 from the explaination and n + 3 results from (n + 2) + 1. I thought about how I could make this less confusing but it just became more confusing in my mind, so just used n in both cases.

I'm now seeing that they're different. However, this sounds a bit off to me:

>n + 3 is the value after n XOR n + 1 XOR n + 2, so the n in the array index expression is n + 2 from the explaination and n + 3 results from (n + 2) + 1.

The reason I think it's off is that array index expression the start of the sum is 1, but in the explanation the start of the sum is n. So I don't think it's as simple as the ending being different by 2.

Re: That XOR Trick (2020)

#135

Post by danbruc » Fri, Jul 04, 2025, 6:54 AM UTC

Thorrez wrote: post #134

danbruc wrote: post #87

Earlier quoted context omitted.

No, that is correct, those two n represent slightly different things. n + 3 is the value after n XOR n + 1 XOR n + 2, so the n in the array index expression is n + 2 from the explaination and n + 3 results from (n + 2) + 1. I thought about how I could make this less confusing but it just became more confusing in my mind, so just used n in both cases.

I'm now seeing that they're different. However, this sounds a bit off to me: >n + 3 is the value after n XOR n + 1 XOR n + 2, so the n in the array index expression is n + 2 from the explaination and n + 3 results from (n + 2) + 1. The reason I think it's off is that array index expression the start of the sum is 1, but in the explanation the start of the sum is n. So I don't think it's as simple as the ending being…

In the array expression the array values and the index depend on n and both vary, in the explanation the n is fixed. Let us do an example starting at say 8.

  n =  8   [  8, 1,  9, 0 ][ 8 % 4] =  8 = n
  n =  9   [  9, 1, 10, 0 ][ 9 % 4] =  1 
  n = 10   [ 10, 1, 11, 0 ][10 % 4] = 11 = n + 1
  n = 11   [ 11, 1, 12, 0 ][11 % 4] =  0

  n =  8   n                         = 8               =  8 = n
           n ^ n + 1                 = 8 ^ 9           =  1
           n ^ n + 1 ^ n + 2         = 8 ^ 9 ^ 10      = 11 = n + 3
           n ^ n + 1 ^ n + 2 ^ n + 3 = 8 ^ 9 ^ 10 ^ 11 =  0

So in the explanation we get 11 = n + 3 still with reference to the starting value n = 8, in the array expression on the other hand we have moved on to n = 10 when we pull 11 = n + 1 out of the array.

Re: That XOR Trick (2020)

#136

Post by betasilly » Fri, Jul 04, 2025, 7:20 AM UTC

Pompidou wrote: post #132

iotasilly wrote: post #58

Since J allow you to write short code, here are three example in J. The first use iota1000, the second a random permutation, and the third use matrix notation to create a little guessing game. Example 1: Find the missing number xor =: (16 + 2b0110) b. iota1000 =: (i. 1000) missingNumber =: (xor/ iota1000) xor (xor/ iota1000 -. 129) echo 'The missing number is ' , ": missingNumber This print 'The missing number is 129…

the top comment trick [ n, 1, n + 1, 0 ][n % 4] can be implemented in J as following : f =: ]`1:`>:`0:@.(4&|)"0 Then: (,. ; #: ; [: #: f) i.16 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 2 0 0 1 0 0 0 1 1 3 0 0 1 1 0 0 0 0 4 0 1 0 0 0 1 0 0 5 0 1 0 1 0 0 0 1 6 0 1 1 0 0 1 1 1 7 0 1 1 1 0 0 0 0 8 1 0 0 0 1 0 0 0 9 1 0 0 1 0 0 0 1 ....

Hello fellow J programmer. In statistic you can estimate the population size by coloring fishes that you put in a lake and some time later you fish in that lake, the proportion of colored fishes allow you to estimate the size of the population. Four month ago I posted some J identities [1] and you were the only one which commented, that means that in this capture I only got one fish and it was the colored fish. This imply that there must be very few J programmers HN, or more precisely, very few of them that post J related material.

The parent's comment (also mine) has a style that was designed not to scare non J programmers. One should also consider that some people dislike J code so downvotes are the usual result except when the post provides some additional insight.

Finally, thank you for this small J lesson, is a pleasure to find here fellow J programmers.

[1] https://news.ycombinator.com/item?id=42859077

Re: That XOR Trick (2020)

#137

Post by less_less » Fri, Jul 04, 2025, 8:05 AM UTC

nullc wrote: post #131

less_less wrote: post #107

Earlier quoted context omitted.

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 so…

Yesterday I linked to an implementation (with complexity quadratic in the number of errors) I helped to create in another comment in this thread. > constant factor using Chien's search algorithm Chien's search is only really reasonable for small field sizes... which I think doesn't really make sense in this application, where the list is long and the missing elements are relatively few. Fortunately in characteristic…

Oh yeah, factoring the polynomial is also a good idea. For a long enough list that ought to be better than AFFT too.

Re: That XOR Trick (2020)

#138

Post by [deleted] » Fri, Jul 04, 2025, 8:51 AM UTC

tromp wrote: post #52

It's funny how the author fails to apply the XOR trick in the two missing values problem: > We can thus search for u by applying this idea to one of the partitions and finding the missing element, and then find v by applying it to the other partition. Since you already have u^v, you need only search for u, which immediately gives you v.

[deleted]

Re: That XOR Trick (2020)

#139

Post by danbruc » Fri, Jul 04, 2025, 10:36 AM UTC

danbruc wrote: post #135

Thorrez wrote: post #134

Earlier quoted context omitted.

I'm now seeing that they're different. However, this sounds a bit off to me: >n + 3 is the value after n XOR n + 1 XOR n + 2, so the n in the array index expression is n + 2 from the explaination and n + 3 results from (n + 2) + 1. The reason I think it's off is that array index expression the start of the sum is 1, but in the explanation the start of the sum is n. So I don't think it's as simple as the ending being…

In the array expression the array values and the index depend on n and both vary, in the explanation the n is fixed. Let us do an example starting at say 8. n = 8 [ 8, 1, 9, 0 ][ 8 % 4] = 8 = n n = 9 [ 9, 1, 10, 0 ][ 9 % 4] = 1 n = 10 [ 10, 1, 11, 0 ][10 % 4] = 11 = n + 1 n = 11 [ 11, 1, 12, 0 ][11 % 4] = 0 n = 8 n = 8 = 8 = n n ^ n + 1 = 8 ^ 9 = 1 n ^ n + 1 ^ n + 2 = 8 ^ 9 ^ 10 = 11 = n + 3 n ^ n + 1 ^ n + 2 ^ n + 3…

Amendment to the parent comment. Note that the arrays contain values like 9 and 10 that are not the XOR of 1 to n for any n but they will also never be accessed because when they appear in the array, then the index used will point to a different element.

Also because we end up back at zero when ever n % 4 == 3, there is some flexibility about the starting point. I wrote 1 to n because that is what the article used, but it would be mathematically cleaner to start at zero which actually changes nothing because XORing with zero does nothing. And we do not have to start at zero at all, we can start at any number divisible by four and less than n because the running XOR sum will become zero just before each multiple of four. So XORing together 0...n, 1...n, 4...n, 8...n or generally 4k...n will give the same result. The explanation part looked at one cycle starting at 4k and ending at 4k + 3 with the running XOR sum being back at zero. Maybe this would have been the less confusing explanation, just using 4k instead of using n again with the constraint that it is divisible by four.

Re: That XOR Trick (2020)

#140

Post by Thorrez » Sat, Jul 05, 2025, 7:07 AM UTC

danbruc wrote: post #139

danbruc wrote: post #135

Earlier quoted context omitted.

In the array expression the array values and the index depend on n and both vary, in the explanation the n is fixed. Let us do an example starting at say 8. n = 8 [ 8, 1, 9, 0 ][ 8 % 4] = 8 = n n = 9 [ 9, 1, 10, 0 ][ 9 % 4] = 1 n = 10 [ 10, 1, 11, 0 ][10 % 4] = 11 = n + 1 n = 11 [ 11, 1, 12, 0 ][11 % 4] = 0 n = 8 n = 8 = 8 = n n ^ n + 1 = 8 ^ 9 = 1 n ^ n + 1 ^ n + 2 = 8 ^ 9 ^ 10 = 11 = n + 3 n ^ n + 1 ^ n + 2 ^ n + 3…

Amendment to the parent comment. Note that the arrays contain values like 9 and 10 that are not the XOR of 1 to n for any n but they will also never be accessed because when they appear in the array, then the index used will point to a different element. Also because we end up back at zero when ever n % 4 == 3, there is some flexibility about the starting point. I wrote 1 to n because that is what the article used, b…

It makes sense to me now. Thanks for taking the time to explain it!