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

91–100 of 181 posts

Re: A neat XOR trick

#91

Post by nerder92 »

DonHopkins wrote: post #74

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

I ran the unoptimized version of the code into ChatGPT and he was able to optimize it similarly to OPs solutions.

I was quite impressed, here is the ChatGPT version:

fn run(s: &[char], window_size: usize) -> usize { let mut unique_chars = 0; for i in 0..window_size { unique_chars |= 1 

    for i in 1..s.len() - window_size {
        let prev = s[i - 1] as u32 - 'a' as u32;
        let next = s[i + window_size - 1] as u32 - 'a' as u32;
        unique_chars ^= 1
}

//NOTE: my prompt was the make the code O(N)

Re: A neat XOR trick

#92

Post by [deleted] »

bsza wrote: post #87

W cannot be larger than the size of the character set, so even the first algorithm runs in O(N) time. It's a cool trick, but it didn't make the algorithm asymptotically more efficient as the OP suggests.

[deleted]

Re: A neat XOR trick

#93

Post by mafuy »

rytis wrote: post #42

I wonder how long before this question starts popping up in interviews with immediate reject if one does not come up with magic-xor solution in 5 minutes on the whiteboard. EDIT: neat solution nonetheless!!

This was basically part of a public set of Google interview questions around 2009 already ;)

Re: A neat XOR trick

#94

Post by ajnin »

DonHopkins wrote: post #74

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

It's also overlooking that there is an actual hero named X-OR, which is the French name of Space Sheriff Gavan, a somewhat popular (at least in France) Japanese show of the prolific "heroes in shiny suits and rubbery monsters from space" genre.

https://fr.m.wikipedia.org/wiki/X-Or

Re: A neat XOR trick

#97

Post by mkeeter »

polynomial wrote: post #80

I am wondering why the bit masks are Big (not Little) Endian? I'm sure there's a reason the example is done that way, I just don't know what it is.

I wanted to put the 1 visually close to the equal sign, so you didn't have to scan all the way to the end of 0000000000000000000000000000000 to find it. Perhaps this is misleading, because the code places the set bit at the LSB!

Re: A neat XOR trick

#98

Post by thomasahle »

nynx wrote: post #90
thomasahle wrote: post #89

One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit. This could happen if we are instead interested in a window of unique words in a long document. Amazingly there is still a solution based on XOR! It is a variant of Bloom Filters, which I know everyone loves, but it uses XOR instead of OR to combine things. Basically each word is hashed to three…

This article’s technique can definitely expand into dynamically allocated bitsets.

Say we don't want to allocate memory dynamically though. We just want to allocate O(W) bits at the start of the program. Can you still do it?

Re: A neat XOR trick

#99

Post by peeters »

Note that for enumerable domains of less than 64, using a long plus bit ops has been a standard Set implementation for quite a while. For example, Java's EnumSet uses a long if the enum has less than 64 values:

https://github.com/frohoff/jdk8u-jdk/blob/master/src/share/c...

Where add() uses `|= bitmask`, remove() uses `&= ~bitmask`, and size() uses a count of the 1's in the long.

Adding XOR as an efficient toggle would be interesting, but unnecessary to keep this O(n), if I understand correctly. It's just toggling the value, so (albeit with an extra branch), you could implement it as:

    if (!set.contains(val)) {
      set.add(val);
    } else {
      set.remove(val);
    }

Re: A neat XOR trick

#100

Post by thomasahle »

bsza wrote: post #87

W cannot be larger than the size of the character set, so even the first algorithm runs in O(N) time. It's a cool trick, but it didn't make the algorithm asymptotically more efficient as the OP suggests.

You could imagine a much larger character set though. For example you might be interested in a sliding window of unique words instead.
Post reply on HN