Something about seeing fun bit tricks solving higher level problems is exciting. As someone who writes higher level software in general using golang/rust/python to solve "boring business" problems, seeing someone using XORs to accomplish something feels like leaving my house and going camping for the weekend.
A neat XOR trick
61–70 of 181 posts
Re: A neat XOR trick
#62That's a nice low level solution the problem - I have to confess that I just wrote a regular expression for it :)
Re: A neat XOR trick
#63'e' ^ 'f' ^ 'g' == 0x40. Uh-oh.
Edit: I misread the post; my bad. The post effectively uses a bit vector to store the last N chars in a window, and the bit vector happens to fit in a single machine word. Also, XOR happens to be a good way to update the bit vector, because it turns out it's sufficient to store how many times each character appears in the window mod 2.
So to be clear, my "demonstration" above only works because the ASCII representations of e, f, and g are not linearly independent with respect to xor. However in the article, the representations of all of the characters are chosen to be a linearly independent set.
Re: A neat XOR trick
#64Earlier quoted context omitted.
And how do you remove the character leaving the window on the left? I don’t think this solution works the way you think it does…
Yes, I wrote it too quickly you would have to xor characters in and out instead. I doubt it is worth it vs popcnt at that point It doesn’t change the fact that problem is incremental, and most importantly you can early exit windows as soon as you discover a single non-unique character. You don't have to wait till the end of the window. They don’t implement this for hash set, for example. Since most (n>1) windows are…
Bit operations are fast, branches are slow.
Re: A neat XOR trick
#65Note that you could also solve this with AND/OR, with just a little more complexity. To “turn on” the bit for the new leading character as you slide the window forward, you of course OR it with the bitmask for the window, and to “turn off” the bit for the old trailing character, you AND its complemented bit-value with the bitmask. Not as elegant as XOR, but still works, and shows that XOR properties aren’t essential to the solution.
Re: A neat XOR trick
#66FTR: This can be done with "only" two loops (opposed to the "naive" 3 in the article) -- without any extra data structures. It's sufficient to keep track of how many characters have been unique so far. For each "new" character, check whether it's different from all of them. If so, increase count. Otherwise, reset count to the distance to the match. def main(): count = 1 for i in range(1, len(SIGNAL)): for j in range(…
That was my conclusion too, this is a super easy problem with a fixed window length. The bit hashing is neat but I was too confused by what seemed to be an over-complication of the problem to really appreciate it. Did you and I both miss something here?
Re: A neat XOR trick
#67Earlier quoted context omitted.
OR wouldn't work with a sliding window since it can't be inverted? This should work: init bit mask and count of bits to 0 for each new char: old = bit mask bit mask = bit mask XOR old char if bitmask > old then count++ else count-- old = bit mask bit mask = bit mask XOR new char if bitmask > old then count++ else count-- if count == window length: return match The idea is that each XOR will always set or clear exactl…
My guess is, it’s still faster to just check whether hashset.insert returns false. Since most windows are not unique early exit will likely beat faster processing.
I doubt the hashmap would beat the XOR method from the article. Hashmaps means allocations, and it means hashing. Hashing is going to be at least as much work as XORing a couple values in the mask. Hashmaps also means chasing pointers all over memory and ruining your cache.
You can add an early return to the OPs XOR method by just checking if the char is already in the bit mask. This will be faster if the word size is large.
Re: A neat XOR trick
#68Am I the only one bothered that he didn't first optimize the HashSet solution to O(N)? When sliding the window, you increase the counter for the new element, decrease the counter for leaving element, and update for each element how many have their counter set to 1. That makes a bit weaker the case for using popcount, since that actually is O(W/Wordsize), which happens to be O(1) in this case.
Thank you. I was wondering the same thing and I think the article is overfocusing on "cool bit tricks" while this simple approach works just fine.
Re: A neat XOR trick
#69Earlier quoted context omitted.
You can combine the two XORs: new_mask = old_mask XOR old_char XOR new_char count += signum(new_mask - old_mask) Where signum(x) = (x > 0) - (x < 0)
If the old and new char are different, two bits will have changed state and comparing the old and new mask will have unreliable results. e.g. old mask = 011100 new mask = 001111, numerically less even though it has one more bit set
Dangit! I concede…
Re: A neat XOR trick
#70Note that you could also solve this with AND/OR, with just a little more complexity. To “turn on” the bit for the new leading character as you slide the window forward, you of course OR it with the bitmask for the window, and to “turn off” the bit for the old trailing character, you AND its complemented bit-value with the bitmask. Not as elegant as XOR, but still works, and shows that XOR properties aren’t essential…
If the same character occurs twice in the window, the second OR will have no effect but the AND will remove it.
The trick is that XOR will leave the bit set if there is an odd number of occurrences, and the only way to have the bit count equal the window size is if every char is unique.