Bitwise Hashing and Randomization

May 2026 · 24 min read

Hashing often relies on bit operations to mix values quickly. XOR hashing is reversible and composable, Zobrist hashing represents sets or board states, and SplitMix64-style mixers defend unordered maps from weak input patterns.

XOR Hashing

XOR is useful when elements can be added and removed symmetrically.

uint64_t h = 0;
h ^= random_value[item]; // add item
h ^= random_value[item]; // remove same item

Because x ^ x = 0, toggling the same element twice cancels it. This is perfect for parity sets, but not for multisets with counts beyond parity unless you add more structure.

Zobrist Hashing

Zobrist hashing assigns a random 64-bit number to every possible atomic feature. A state hash is the XOR of features present in the state.

// Chess-like example:
hash ^= rnd[piece][square]; // place/remove a piece
hash ^= rnd_side_to_move;   // toggle side to move

It is popular in game engines and can be useful in CP for randomized state comparison.

SplitMix64 Mixer

This mixer spreads nearby integers across the 64-bit space.

uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
    x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

Custom Hash for unordered_map

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

Collision Thinking

Randomized 64-bit hashes are probabilistic. Collision probability is tiny for normal CP use, but not impossible. For correctness-critical tasks, use deterministic structures or double hashing when appropriate.

Pitfalls

• XOR hash loses multiplicity parity: two equal items cancel.
• Do not expose random hashes as proof in formal algorithms unless probability is acceptable.
• Hash mixing helps performance; it does not change asymptotic complexity.
• Use unsigned overflow intentionally; signed overflow is undefined.

Practice Problems

• LeetCode 187 - Repeated DNA Sequences rolling bits 2-bit encoding per nucleotide.
• LeetCode 318 - Maximum Product of Word Lengths mask hash compare character sets as integers.
• Codeforces - Anti-hash discussions custom hash understand why mixers are used.