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

41–50 of 181 posts

Re: A neat XOR trick

#41

Post by DannyBee »

nebulous1 wrote: post #39
DannyBee wrote: post #31

Earlier quoted context omitted.

Well, actually, in this case, no, POPCNT is unnecessary here, since you don't actually have to count anything. you only need to know if the bitmask changed when you added a new character ;) But otherwise, yes. I spent quite a while optimizing GCC's bitmap operations years ago, including implementing some new sparse bitmap types, and the sparse bitmap types i implemented ended up dependent on the speed of popcnt and f…

it's not sufficient that the newest character in the window is unique? the older characters need to be unique too.

I posted how to do it in another comment on the thread.

Re: A neat XOR trick

#42

Post by rytis »

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!!

Re: A neat XOR trick

#43

Post by rep_lodsb »

DannyBee wrote: post #41
nebulous1 wrote: post #39

Earlier quoted context omitted.

it's not sufficient that the newest character in the window is unique? the older characters need to be unique too.

I posted how to do it in another comment on the thread.

Input: "abccdef"

Your algorithm will report a match at "bccd" since the "a" wasn't removed from the bitmask.

Re: A neat XOR trick

#45

Post by qsort »

NathanaelRea wrote: post #29

Isn't the memory just O(Unique) since the window size is bounded by the max number of unique characters (in this case 26)? In the general case, the hash would need to store one bit for each unique element. If you use a bit mask, you allocate all the memory up front. In a set you allocate through runtime, but could just use set.add(char - 'a') for a similar memory bound. But both need to be able to store every unique…

Yes. It's a neat trick, but from an algorithmic point of view it's exactly the same as the obvious solution, replacing a set with a hash-set. I did this with a counter in python:

  def first_diff(s, n):
      cnt = Counter()

      for i, c in enumerate(s, 1):
          cnt[c] += 1
          if i > n:
              top = s[i - n - 1]
              cnt[top] -= 1
              if cnt[top] == 0:
                  del cnt[top]
          if len(cnt) == n:
              return i

Re: A neat XOR trick

#46

Post by nebulous1 »

DannyBee wrote: post #41
nebulous1 wrote: post #39

Earlier quoted context omitted.

it's not sufficient that the newest character in the window is unique? the older characters need to be unique too.

I posted how to do it in another comment on the thread.

If you're using OR (unlike the OP) how are you removing the left side of the window? And still, even if the newest character is unique, previous characters might not be

Re: A neat XOR trick

#47

Post by meindnoch »

DannyBee wrote: post #26

You don't need to count ones at all, because you can stop looking at a window as soon as you discover it's not unique. As a result, you only have to detect if the bitmask is changed from adding a new character, not how many one bits there are in it. (This is true in the hash-set version as well - if insert returned false you can move on). old bit mask = current bit mask current bit mask = current bit mask OR new char…

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…

Re: A neat XOR trick

#48

Post by DannyBee »

rep_lodsb wrote: post #40
DannyBee wrote: post #26

You don't need to count ones at all, because you can stop looking at a window as soon as you discover it's not unique. As a result, you only have to detect if the bitmask is changed from adding a new character, not how many one bits there are in it. (This is true in the hash-set version as well - if insert returned false you can move on). old bit mask = current bit mask current bit mask = current bit mask OR new char…

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.

Re: A neat XOR trick

#49

Post by DannyBee »

rep_lodsb wrote: post #43
DannyBee wrote: post #41

Earlier quoted context omitted.

I posted how to do it in another comment on the thread.

Input: "abccdef" Your algorithm will report a match at "bccd" since the "a" wasn't removed from the bitmask.

Yes, you are correct you would have to xor them back out

Re: A neat XOR trick

#50

Post by DannyBee »

meindnoch wrote: post #47
DannyBee wrote: post #26

You don't need to count ones at all, because you can stop looking at a window as soon as you discover it's not unique. As a result, you only have to detect if the bitmask is changed from adding a new character, not how many one bits there are in it. (This is true in the hash-set version as well - if insert returned false you can move on). old bit mask = current bit mask current bit mask = current bit mask OR new char…

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 not unique (well, more accurately the probability of the window being unique decreases as the size of the window approaches the number of possible characters), early exit from windows will likely beat bit munging except for small windows, until you get into SIMD solutions.

Post reply on HN