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

51–60 of 141 posts

Re: That XOR Trick (2020)

#51

Post by lblume »

repiret wrote: post #26
anitil wrote: post #7

Earlier quoted context omitted.

It really tickles my brain in a lovely way that it avoids all overflow risk as well

There is no overflow risk. The trick works on any Abelian group. N-bit values form an Albanian group with xor where 0 is the identity and every element is its own inverse. But N-bit values also form an Abelian group under addition with overflow, where 0 is the identity and 2s-compliment is the inverse. If you’re working on an architecture where a single multiplication and a bit shift is cheaper than N xor’s, and wher…

You can also calculate the XOR-accumulation of all values between 1 and n in O(1) using a lookup table like this:

    [n, 1, n+1, 0][n%4]

Re: That XOR Trick (2020)

#52

Post by tromp »

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.

Re: That XOR Trick (2020)

#53

Post by codebje »

haskellshill wrote: post #42
moron4hire wrote: post #35

Earlier quoted context omitted.

Did I not say that?

>we end up performing two loops instead of one, all because sticking three operations in one statement is "yucky" You seem to believe that "O(2 n)" for value in range(1, n + 1): result ^= value for value in A: result ^= value is slower than "O(n 2)" for value in range(1, n + 1): result ^= value result ^= A[value-1] simply because the latter has one "for loop" less. Am I misunderstanding you, or if not, why would this…

None of this is as straightforward as it seems.

A "for" loop in Python isn't particularly cheap. It compiles to some static overhead to set up the iterator, then each loop iteration compiles to the "FOR_ITER" opcode, a "STORE_FAST" opcode to assign the iteration value to a variable, and the body of the loop.

"FOR_ITER" calls the "__next__()" method of the iterator (which is on top of the interpreter object stack), catches the StopIteration exception to know when to terminate the loop (by jumping past the loop body), and stores the iterator value to the top of the stack. What "__next__()" does is totally opaque - we don't know what kind of object A is - but since we've added the overhead of a function call already it wouldn't matter if it was a super tight bit of machine code, we're already paying a (relatively) hefty runtime cost.

A particularly bad implementation of "__next__()" for some custom iterable collection might be so stupid as to walk through the collection until it reaches the current index's item and returns that, so "for value in A" could in fact be O(n^2).

Plus, "result ^= A[value-1]" is substantially more work than "result ^= value", so even just on the loop bodies the two examples aren't very similar at all. Evaluating "A[value-1]" may wind up calling a "__getitem__()" method on A.

If A is, say, a linked list or binary tree, iterating it is very cheap but indexing it is O(n), so the second loop might be O(n^2) where the first is O(n).

So maybe we be a bit more Pythonic, and do:

    for i, value in enumerate(A)
        result ^= i
        result ^= value
One loop, no indexing of A! But we've not actually saved anything: the __next__() method of enumerate's iterator will increment its index then call the __next__() method of A's iterator, (approximately) the same work as if we'd done two FOR_ITER, one for an index and one for A.

Why would this matter for speed? I don't know. Unless 'n' is pretty big a human won't even notice the execution time of any of this code.

Re: That XOR Trick (2020)

#54

Post by moron4hire »

haskellshill wrote: post #42
moron4hire wrote: post #35

Earlier quoted context omitted.

Did I not say that?

>we end up performing two loops instead of one, all because sticking three operations in one statement is "yucky" You seem to believe that "O(2 n)" for value in range(1, n + 1): result ^= value for value in A: result ^= value is slower than "O(n 2)" for value in range(1, n + 1): result ^= value result ^= A[value-1] simply because the latter has one "for loop" less. Am I misunderstanding you, or if not, why would this…

Even assuming python's foreach loop in these cases get optimized down to a very bare for loop, the operations being performed are dominated by the looping logic itself, because the loop body is so simple.

Each iteration of a for loop performs one index update and one termination comparison. For a simple body that is just an XOR, that's the difference between performing 5 operations (update, exit check, read array, XOR with value, XOR with index) per N elements in the one loop case versus 7 operations (update, exit, read array, XOR with value, then update, exit, XOR with index) in the two loop case. So we're looking at a 29% savings in operations.

It gets worse if the looping structure does not optimize to a raw, most basic for loop and instead constructs some kind of lazy collection iterator generalized for all kinds of collections it could iterate over.

The smaller the loop body, the higher the gains from optimizing the looping construct itself.

Re: That XOR Trick (2020)

#55

Post by ur-whale »

One interesting problem related to the trick (which as pointed out elsewhere in the thread, fails spectacularly when the two variables alias to the same memory location) is to find other dyadic functions of integers that have the same property.

Re: That XOR Trick (2020)

#57

Post by ur-whale »

motorest wrote: post #44
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.)

> 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 by dissecting the problem step by step and understanding what the code actually does and how.

Bonus if you can see the potential aliasing problem when used to swap two variables.

Not a trivia question at all.

Re: That XOR Trick (2020)

#58

Post by iotasilly »

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'

Example 2: Using a random permutation, find the missing number.

   permuted =: (1000 ? 1000)
   missingNumber = (xor/ permuted) xor (xor/ permuted -. ? 1000)
Example 3: find the missing number in this matrix.

  _ (
Final test: repeat 10 times the example 3 (random matrices) and collect the time it takes you to solve it in a list of times, then compute the linear regression best fit by

  times %. (1 ,. i. 10)
Did you get better at solving it by playing more times?

I am not affiliated with J, but in case you want to try some J code there is a playground: https://jsoftware.github.io/j-playground/bin/html2/

Edited: It seems I am procrastinating a lot about something I have to do but don't want to.

Re: That XOR Trick (2020)

#59

Post by ikurei »

repiret wrote: post #26
anitil wrote: post #7

Earlier quoted context omitted.

It really tickles my brain in a lovely way that it avoids all overflow risk as well

There is no overflow risk. The trick works on any Abelian group. N-bit values form an Albanian group with xor where 0 is the identity and every element is its own inverse. But N-bit values also form an Abelian group under addition with overflow, where 0 is the identity and 2s-compliment is the inverse. If you’re working on an architecture where a single multiplication and a bit shift is cheaper than N xor’s, and wher…

I think they meant that XOR avoids the overflow risk, whereas doing the sum of the array to figure out which number could cause an overflow.
Post reply on HN