Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A neat XOR trick

mattkeeter.com

Post reply on HN
Print view View original

11–20 of 181 posts

Re: A neat XOR trick

#11

Post by nraynaud »

xnorswap wrote: post #2

I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution still runs fast enough that it more than makes up in time spent programming it. There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to…

I love the Sunday quaterbacking of AoC, more than the competition itself (I'm not even doing this year). And I agree with you that a quick reminder that some problems are "naively intractable" is a good wake up call once in a while.

Re: A neat XOR trick

#13

Post by Robin_Message »

n4r9 wrote: post #9

I think the claim at the end is supposed to say `O(D)` running time rather than `O(N)` (or I can't see where `N` is defined). Does this technique catch letters duplicated more than once? In a Python 3 shell: >> 2 ^ 4 6 >> 2 ^ 4 ^ 2 4 >> 2 ^ 4 ^ 2 ^ 2 6 Yes I guess it does, because inputs are used up in order to turn bits on and off. Nice!

The insight is that the only way to get W bits set is for the last W letters to all have been unique. Duplicate letters toggle bits on and off, but never get you any extra 1 bits set.

If you wanted to detect V unique characters from a window of W characters where V < W, this trick wouldn't work. But you could still have a rolling window, it would just be a map counting "how many of this character in the window", which you can increment the relevant character for as it enters the window, and decrement as it leaves.

Re: A neat XOR trick

#14

Post by ladberg »

xnorswap wrote: post #2

I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution still runs fast enough that it more than makes up in time spent programming it. There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to…

If you aren't already familiar with it, you might find projecteuler.net fun!

Re: A neat XOR trick

#16

Post by grogers »

ribit wrote: post #5

One can improve this even further I think. First, using an iterator instead of indexing into an UTF-8 string. Second, using the codepoint value directly as a bitmask (why is author realigning the bit mask to "a" in the first place?)

The author passed the input as &[char] not &str, so indexing is no problem. That's weird in its own right, but obviously not the core of the post.

Re: A neat XOR trick

#17

Post by moloch-hai »

The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.

Re: A neat XOR trick

#19

Post by mkeeter »

n4r9 wrote: post #9

I think the claim at the end is supposed to say `O(D)` running time rather than `O(N)` (or I can't see where `N` is defined). Does this technique catch letters duplicated more than once? In a Python 3 shell: >> 2 ^ 4 6 >> 2 ^ 4 ^ 2 4 >> 2 ^ 4 ^ 2 ^ 2 6 Yes I guess it does, because inputs are used up in order to turn bits on and off. Nice!

> I think the claim at the end is supposed to say `O(D)` running time rather than `O(N)` (or I can't see where `N` is defined).

Good catch; this should be fixed (using N for input length and W for window size consistently in the writeup).

Re: A neat XOR trick

#20

Post by jhoechtl »

> There's no moral to the story, other than "xor is cool"

The moral is knowledge is king and no matter how much iron you throw at a problem a well-designed algorithm will beat it.

Post reply on HN