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

21–30 of 181 posts

Re: A neat XOR trick

#21

Post by WJW »

n4r9 wrote: post #6
xnorswap wrote: post #2

I had considered this approach but the nature of AoC means it rewards real world time to solution rather than and kind of computation time, and a naive solution still runs fast enough that it more than makes up in time spent programming it. There's actually whole classes of problems which would be more interesting if the naive solution wasn't fast enough, for example even on day 7 (or was it 8?) naively exploring to…

Arguably day 11 part 2 is such a "lanternfish" problem, although it essentially tells you to watch out for it.

I definitely ran into that. I read "impractically large number" and thought "well the language I'm using has arbitrary size integers so I should be fine". So, I changed the code from 20 iterations to 10000 iterations and suddenly all 16 GB of my RAM was filled with Santa's worry counters.

Re: A neat XOR trick

#22

Post by dahfizz »

ribit wrote: post #5

One can improve this even further I think. First, using an iterator instead of indexing into an UTF-8 string. Second, using the codepoint value directly as a bitmask (why is author realigning the bit mask to "a" in the first place?)

The point is that each character represents a single bit in the mask, so it's easy to count the whole number of characters using popcount. If you XOR in the characters directly you can no longer easily count which characters are in the set.

Re: A neat XOR trick

#23

Post by gigatexal »

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
} “

Re: A neat XOR trick

#24

Post by jsd1982 »

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 << n sets a 1 bit at the nth bit position. << is the left shift operator.

Re: A neat XOR trick

#25

Post by dahfizz »

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 } “

The "stuff" assigns an integer value to the char. 'b' - 'a' = 1, for example. This assigns each char a unique integer value. By shifting 1 up that many times, you assign a unique bit position to each char.

Re: A neat XOR trick

#26

Post by DannyBee »

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 character
  if old bit mask == current bit mask
    window is not unique, move to the next window
  (otherwise window is so far unique)

Re: A neat XOR trick

#28

Post by adrian_b »

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.

It is good to remember that the instruction POPCNT was introduced for the first time in the instruction set of a computer by Alan Turing, already in 1949, in Ferranti Mark I (as "sideways add").

Unfortunately few other computers have included it before Cray 1, which made it well known, under the current name.

Re: A neat XOR trick

#29

Post by NathanaelRea »

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 element. They are both O(Unique), it just happens that 26 <= num_bits(u32).

Re: A neat XOR trick

#30

Post by brilee »

This trick is called zobrist hashing in chess/go programming. It allows for incremental calculation of the board hash, which is particularly useful because all of the game variations you're exploring are all nearly identical to one another, saving a lot of compute.
Post reply on HN