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

81–90 of 181 posts

Re: A neat XOR trick

#81

Post by alanning »

dahfizz wrote: post #25
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.

For those new to bitshifting, here are the results of the "stuff" operation that @dahfizz describes:

  'a' - 'a' = 0, so take 1 and shift it left 0 times:
  00000000000000000000000000000001 = 'a'

  'b' - 'a' = 1, so take 1 and shift it left 1 time:
  00000000000000000000000000000010 = 'b'

  'c' - 'a' = 2, so take 1 and shift it left 2 times:
  00000000000000000000000000000100 = 'c'
(I'm not sure why the post's author chose to use 10000000000000000000000000000000 as their example for 'a' rather than the above which IIUC is how the code actually works.)

Re: A neat XOR trick

#82

Post by FartyMcFarter »

brilee wrote: post #30

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.

It's reminiscent of Zobrist hashing in that it's an incremental hash calculated with xor. But Zobrist hashing has the crucial difference of using a random k-bit number to be xor'ed into the hash (k is a constant, typically 64 these days) for each member of the set that is present, instead of an N-bit string where N is the number of possible elements in the set.

For example, in a chess engine: if the hash value for "white knight on f3 square" is 0x8BADF00D and the hash value for "white king on e4 square" is 0x1BADB002, then a chess board containing only "white knight on f3 and white king on e4" would be hashed as (0x8BADF00D xor 0x1BADB002) = 0x9000400F.

The upside of this trick is that if your set can contain N different objects (e.g. 768 combinations of 12 different chess pieces on each of 64 squares), you don't need to use an N-bit hash value, which would be pretty big. In the particular problem described in this blog, this isn't an advantage as it's using a set containing only up to 26 letters, which neatly fits in a u32 even if you dedicate a bit to each letter.

However there are downsides to Zobrist hashing - it's very hard to guarantee that you don't get hash collisions in this manner, as AFAIK you'd have to try all combinations of valid sets, which is prohibitively expensive. So every algorithm relying on this hash value either has to be robust to hash collisions, or it accepts a small probability of failure.

Most importantly in this case, Zobrist hashing doesn't let you test whether a particular element is present in the set, nor does it let you count the number of elements in a set. So it wouldn't work as a solution to the problem in this blog, which requires counting how many unique letters are present in the hash value.

Re: A neat XOR trick

#83

Post by thomasahle »

brilee wrote: post #30

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.

Zobrist hashing is different. With Zobrist you have a table pd random numbers. You look each key up in the table and xor the values.

Re: A neat XOR trick

#85

Post by jvanderbot »

This is also essentially the trick applied in Kadane's Algorithm for the "maximum contiguous sum" search, albeit using masks to "undo" the set-of-characters check whereas Kadane's uses subtraction to "undo" the addition for maximum sum check.

https://www.geeksforgeeks.org/largest-sum-contiguous-subarra...

Re: A neat XOR trick

#86

Post by rep_lodsb »

DannyBee wrote: post #79
dahfizz wrote: post #67

Earlier quoted context omitted.

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.

Even if the hashmap library knew that the only valid keys were 'a' .. 'z', it wouldn't be magically faster. The best it could do is use basically the same code as a hand-rolled implementation.

Bit operations and shifts take a single clock cycle, and the mask can be stored in a register throughout the entire loop.

If "early exit" brings any improvement, I don't see why the best wouldn't be to combine the two solutions instead of choosing one or the other.

Re: A neat XOR trick

#87

Post by bsza »

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.

Re: A neat XOR trick

#89

Post by thomasahle »

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 locations and you flip those bits. Then you have to do some probabilistic analysis.

https://arxiv.org/abs/2211.03683

Edit: Actually the technique in this paper would take linear time to determine uniqueness. I wonder if there's a way to do it in constant time...

I guess you could just implement linear probing or cuckoo hashing in bits. But then update time would be amortized constant only.

Re: A neat XOR trick

#90

Post by nynx »

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.
Post reply on HN