# Rabin Karp algorithm that uses bitwise AND

I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here.

Here's the gist of it:

// modulo = 63

for (i=0; i<loops; i++) {
hash -= factor * (s.tokens[i].type & modulo);
hash = (2*hash) + (s.tokens[i+hashLength].type & modulo);
}

What makes this a "good" hash function (or is it a terrible one)?

Couple of things I don't understand:

1. there isn't a modulus applied to the hash at each iteration of the loop unlike the traditional rabin karp algorithm, so is there a "table size" this adheres to, and why?

2. (2*hash) - what is the significance of choosing 2 as the base? In the regular rabin-karp, the base is recommended to be larger than the character set size. 2 certainly isn't.

3. (s.tokens[i+hashLength].type & modulo) - What is the bitwise AND doing here?

• 63 in binary is just 8 set bits in the LSBs and unset bits elsewhere. $x \land m = x \mod (m - 1)$ when $modulo$ is a power of 2. – Throckmorton Apr 25 at 17:40