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

171–180 of 243 posts

Re: That XOR Trick (2020)

#171

Post by kevinventullo »

smlckz wrote: post #30
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

(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1 In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0) Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1 Phew! Can this be mad…

The simplest formula from the OEIS page seems to be

  a(4n)=4n,

  a(4n+1)=1,

  a(4n+2)=4n+3,

  a(4n+3)=0.
Once you have the formula in front of you, it’s easy to prove it by induction. A branchless implementation of this function with no multiplies or divides:

  f(x)=(x^(x&1-1))+(((x+1)&2)>>1)

Re: That XOR Trick (2020)

#172

Post by ravi-delia »

bonoboTP wrote: post #139
bidirectional wrote: post #108

Earlier quoted context omitted.

Google's policy is to extensively discuss interview questions internally, and blacklist any that are leaked. They are still complained about near-constantly on any tangentially related HN thread.

The attitude is often quite strange. Like on Twitter I saw a few days ago that many were riled up about the fact that a prof would ask how to solve Ax=b (linear algebra) for a deep learning / computer vision PhD position. People were calling this unnecessary gatekeeping ... I'm like that's just a warm-up question to get comfortable... But apparently the loud online hive mind opinion is that all that should count is s…

Except solving linear functions has a clear role in any field that makes use of linear algebra. Interviews that require memorizing volumes of pointless trivia unrelated to the work at hand are completely different.

Re: That XOR Trick (2020)

#173

Post by strulovich »

user-the-name wrote: post #129
surajrmal wrote: post #123

Earlier quoted context omitted.

The bigger problem with this approach is that you can't remove/erase something from the list just by knowing it's address. This is a key mechanism for most use cases. However, if you're fine with limiting yourself to erasing only during iteration, it's pretty nifty. I've also done some benchmarks in the past and found it interior iteration performance due to what I'm assuming to be inability to prefetch the next addr…

Also, I think this may be the only data structure I have heard of that has an O(1) reverse ordering operation?

Wouldn’t this be achieved by an array and a Boolean flag just as well?

Re: That XOR Trick (2020)

#174

Post by smlckz »

smlckz wrote: post #30
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

(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1 In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0) Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1 Phew! Can this be mad…

Correction: It is not ~(n & 1), but !(n & 1)

Or ((~n) & 1) as ChrisLomont pointed out

Re: That XOR Trick (2020)

#175

Post by ChrisLomont »

smlckz wrote: post #30
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

(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1 In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0) Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1 Phew! Can this be mad…

> n * ~(n & 1)

This term results in huge numbers. Do you mean n * ((~n)&1)) ?

Re: That XOR Trick (2020)

#176

Post by sleavey »

patrec wrote: post #101
sleavey wrote: post #65

Earlier quoted context omitted.

I sometimes use your "bug" on purpose in tests, when checking that two values are either both defined or both undefined, but not one defined and one undefined: $ python >>> a, b = 1, 2 >>> bool(a) ^ bool(b) False >>> a, b = 1, 1 >>> bool(a) ^ bool(b) False >>> a, b = None, None >>> bool(a) ^ bool(b) False >>> a, b = None, 1 >>> bool(a) ^ bool(b) True (Note: this doesn't work if a value can be 0, because bool(0) is Fa…

You are aware that ^ on a 1 bit value (like a boolean) is just !=, right?

Hah, I wrote that code on the fly and didn't check the aforementioned test implementation, where I had `(a is None) ^ (b is None)` like the other commenter suggested.

Re: That XOR Trick (2020)

#177

Post by viraptor »

fh973 wrote: post #67

Surprised this doesn't have my favorite XOR trick: implementing a double-linked list with one pointer! Store predecessor XOR successor in each node. I suspect this clicks already with everyone, and I don't need to explain forward and backward iteration.

What it doesn't click with is GC. Any pointer xor trick will fail when trying to add a GC to the app, because the pointers don't point at the right thing anymore.

Re: That XOR Trick (2020)

#178

Post by sleavey »

shiftingleft wrote: post #73
sleavey wrote: post #65

Earlier quoted context omitted.

I sometimes use your "bug" on purpose in tests, when checking that two values are either both defined or both undefined, but not one defined and one undefined: $ python >>> a, b = 1, 2 >>> bool(a) ^ bool(b) False >>> a, b = 1, 1 >>> bool(a) ^ bool(b) False >>> a, b = None, None >>> bool(a) ^ bool(b) False >>> a, b = None, 1 >>> bool(a) ^ bool(b) True (Note: this doesn't work if a value can be 0, because bool(0) is Fa…

Your note is very important, I think it would be good to give it more emphasis. What works flawlessly, however, is: In [1]: a = None In [2]: b = 0 In [3]: (a is None) ^ (b is None) Out[3]: True Alternatively, as suggested in another comment, you can use inequality as a replacement for XOR: In [4]: (a is None) != (b is None) Out[4]: True Another error prone pattern is the following: In [5]: a or b Out[5]: 0 Which can…

Lesson for myself: check my working. The test I actually used the XOR in, that I was referring to, uses the first example you wrote - I agree, this is much better. However, I also like your second example, which is arguably clearer. Thanks!

Re: That XOR Trick (2020)

#179

Post by smlckz »

ChrisLomont wrote: post #175
smlckz wrote: post #30

Earlier quoted context omitted.

(n+1)%2 = if (n+1) is divisible by 2 then 0 else 1 = (n+1) & 1 = ~(n & 1) ((n + (n % 2)) // 2) % 2 = ((n + (n & 1)) >> 1) & 1 = ((n & 2) >> 1) ^ (n & 1) = (n ^ (n >> 1)) & 1 In human terms, that means XOR of 1, 2, ..., n is: (if (n is divisible by 2) then n else 0) + (if ((if (n is divisible by 2) then n else n + 1) is divisible by 4) then 1 else 0) Or, as code: n * ~(n & 1) + (n ^ (n >> 1)) & 1 Phew! Can this be mad…

> n * ~(n & 1) This term results in huge numbers. Do you mean n * ((~n)&1)) ?

My bad. Thanks for pointing it out.

Re: That XOR Trick (2020)

#180

Post by epsilon-greedy »

j-pb wrote: post #10

Ah off by one errors are hard: > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 1] should be > 1 ^ 2 ^ ... ^ n ^ A[0] ^ A[1] ^ ... ^ A[n - 2] Because a 0 indexed array of length n-1, has n-2 as it's last index. After all, it's missing a value.

Author here (Florian): I just fixed this. Very good catch. Off-by-one errors are hard indeed. :)
Post reply on HN