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

71–80 of 181 posts

Re: A neat XOR trick

#71

Post by dukoid »

flatline wrote: post #66
dukoid wrote: post #53

FTR: 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?

I don't think so. As much as I love using bit operations: in this case I'd actually prefer a table of character counts for a "true" O(n) solution, as bit counting isn't guaranteed to be a "native" operation.

Re: A neat XOR trick

#72

Post by jandrese »

SaddledBounding wrote: post #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 work…

The example code in the article left out the lookup table to convert each character into a single bit representation. All the tricky xor and popcount stuff could have been a 26 byte array just as easily and been O(n).

Re: A neat XOR trick

#73

Post by robinhouston »

jandrese wrote: post #72
SaddledBounding wrote: post #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 work…

The example code in the article left out the lookup table to convert each character into a single bit representation. All the tricky xor and popcount stuff could have been a 26 byte array just as easily and been O(n).

There's no lookup table. The example code in the article does the conversion using this expression:

    1

Re: A neat XOR trick

#74

Post by DonHopkins »

Of all the combinational logic functions, XOR is the coolest. Even its name is cool! It sounds like an evil super hero, or an ancient god.

ChatGPT did offer a useful suggestion I'd never heard of when I asked it to describe The Mighty XOR:

>As I mentioned in my previous responses, XOR is a logical operation and does not have any physical form or abilities, so it cannot be a superhero. Therefore, it is not possible for a character named "The Mighty XOR" to be part of the Marvel universe or any other fictional universe, as they would not exist in reality. If you are interested in characters from the Marvel universe with powers related to digital logic or computing, you might consider the character of The Calculator from DC Comics, who has the ability to use his super-genius intellect to perform complex calculations and hack into computer systems. However, this character is not part of the Marvel universe and does not have the name "The Mighty XOR".

https://en.wikipedia.org/wiki/Calculator_(character)

>Calculator (Noah Kuttler) is a supervillain appearing in American comic books published by DC Comics. Originally introduced as one of many villains in Batman's rogues' gallery, the character was later redeveloped in the 2000s as a master information broker, hacker, and tactical supervisor to other supervillains, and foil to Batman's partner Oracle.

>[...] Calculator suffers from severe obsessive-compulsive disorder, unbeknownst to his peers (even though this was hinted at when he was in charge of monitoring Supergirl), and initially controlled this with medication.

Re: A neat XOR trick

#75

Post by OJFord »

gigatexal wrote: post #23

Can someone explain the 1 “ fn run(s: &[char], window_size: usize) -> usize { let mut set = 0u32; for i in 0..s.len() { // Turn on bits as they enter the window set ^= 1 // Turn off bits as they leave the window if i >= window_size { set ^= 1 } “

'1 'Stuff' there is just any expression (to understand separately) that evaluates to the number of positions to shift; `>`).

In brief `(s[i - window_size] as u32 - 'a' as u32)` is finding the character that just left the window on the left, represented as a number, starting from 'a' as 0 so that all 26 fit inside 32 bit positions.

Re: A neat XOR trick

#76

Post by quietbritishjim »

SaddledBounding wrote: post #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 work…

Ah OK, the article is actually suggesting making a list of Booleans whose length equals the number of possible characters. It just happens that it's assuming 26 allowed characters which fit in the bits of a 64 bit number.

The running time is does not depend on the window length, but does depend on the number of possible characters. If it's all of Unicode for example you'd be stuffed: you could fix the vector of values in memory (currently there are approx. 150,000 unicode code points), even if you used a byte per value, but counting number of true values will require iterating over the whole vector.

Even just going from 26 Latin letters to 256 byte values makes this trick quite messy unless your language has a really nice bit vector type (admittedly many do).

This comment was helpful for me to understand what was going on, even though it's a mistake followed by a correction.

Re: A neat XOR trick

#77

Post by DannyBee »

rep_lodsb wrote: post #64
DannyBee wrote: post #50

Earlier quoted context omitted.

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.

Well, yes, but most of these branches can be if-converted into conditional moves anyway if you want.

So they are data dependencies and not control ones. There are still some control ones.

Beyond that, let me be super clear: Imagine the following six versions:

1. One window at a time processing. No early exit, no bit munging.

2. One window at a time processing. No early exit, bit munging.

3. One window at a time processing. You don't use direct bit munging, but you early exit the window when you hit the non-unique character, and skip the window forward to the first instance of that non-unique character.

IE given "hmma", n=4, you early exit at the second m, and skip processing windows forward to right after the first m (since no window prior to that can be unique, as they will all hit the double m)

4. One window at a time processing, bit munging, same otherwise as #3

5. Sliding window processing, no bit munging

6. Sliding window processing, bit munging.

The speedup between the 1-2 vs 3-6 is much greater than 5 vs 6 and 3 vs 4.

You could probably make 3 pretty darn competitive with 6, and 4 could probably beat 6 with SIMD (IE processing multiple windows in parallel really fast, and maybe wasting work, vs guaranteeing you only do the minimum work to find a unique window)

Re: A neat XOR trick

#79

Post by DannyBee »

dahfizz wrote: post #67
DannyBee wrote: post #48

Earlier quoted context omitted.

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

the domain/range is fixed, so you don't have to allocate, actually, because you can have a fixed sized table and perfect hash :)

That said, I agree you can make the bit munging faster in the end, i'm just saying i don't think the speed up is anywhere near the improvement from early-exiting.

Post reply on HN