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

51–60 of 181 posts

Re: A neat XOR trick

#51

Post by meindnoch »

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…

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)

Re: A neat XOR trick

#52

Post by actionfromafar »

DannyBee wrote: post #49
rep_lodsb wrote: post #43

Earlier quoted context omitted.

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

I swear I have seen this conversation before. A glitch?

Re: A neat XOR trick

#53

Post by dukoid »

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(0, count):
        if SIGNAL[i - j - 1] == SIGNAL[i]:
          count = j
          break

      count = count + 1
  
      if count == 4:
        print(i + 1)
        break
If we consider the word length a constant this should be O(n).

Re: A neat XOR trick

#54

Post by TYMorningCoffee »

DannyBee wrote: post #37
mihaic wrote: post #35

Am 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.

You don't even have to do this. If HashSet.insert ever returns false, the character was already in the set, and the window is not unique, so you can early exit and move on. If you get through the window without insert returning false, it is unique. You don't need to do anything else (like check the length of the hash set at the end)

I think he meant to use a hash map plus a numOfOnes counter instead of hash set. With a hash map, you don't need to build the entire window every loop. It's only a constant amount of work per iteration, achieving O(N)

Re: A neat XOR trick

#55

Post by snvzz »

moloch-hai wrote: post #17

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.

>RISC-V

Doesn't B have a POPCNT?

B is mandatory in RVA22.

Re: A neat XOR trick

#56

Post by DannyBee »

actionfromafar wrote: post #52
DannyBee wrote: post #49

Earlier quoted context omitted.

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

I swear I have seen this conversation before. A glitch?

No - he responded on both parts of the thread where i commented. I started to respond here as well, then updated it to redirect to the other comment so we don't end up with two long threads.

Re: A neat XOR trick

#57

Post by [deleted] »

moloch-hai wrote: post #17

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.

[deleted]

Re: A neat XOR trick

#58

Post by cbm-vic-20 »

snvzz wrote: post #55
moloch-hai wrote: post #17

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.

>RISC-V Doesn't B have a POPCNT? B is mandatory in RVA22.

These are the cpop and cpopw instructions.

https://github.com/riscv/riscv-bitmanip/blob/main/bitmanip/i...

Re: A neat XOR trick

#59

Post by DannyBee »

TYMorningCoffee wrote: post #54
DannyBee wrote: post #37

Earlier quoted context omitted.

You don't even have to do this. If HashSet.insert ever returns false, the character was already in the set, and the window is not unique, so you can early exit and move on. If you get through the window without insert returning false, it is unique. You don't need to do anything else (like check the length of the hash set at the end)

I think he meant to use a hash map plus a numOfOnes counter instead of hash set. With a hash map, you don't need to build the entire window every loop. It's only a constant amount of work per iteration, achieving O(N)

Yes. You can slide a hash map and a counter, as we went through below. You can also replace the hash map with a bitmask to store the set.

You actually don't need any extra anything at all if you want, as you can just keep a single count because you don't need to look back at old windows, and can keep moving forward to the last non-unique point, making it O(N).

I'm sure this being HN, someone will come along and post how to do this.

I already got caught out once by trying to code it too fast so not gonna do it ;)

Re: A neat XOR trick

#60

Post by rep_lodsb »

meindnoch wrote: post #51
rep_lodsb wrote: post #40

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

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

Post reply on HN