# Perfect hash function that weakly preserves leading zeros

I need a perfect hash function that maps 2 integers into one integer twice the size (i.e. $$(Int64, Int64) \rightarrow Int128$$).

The function preserves sum of leading zero bits:

• $$(0, 0) \rightarrow 0$$ - good mapping, as each argument has $$64$$ leading zeros and that transformed into $$128$$ leading zeros of the output
• $$(0, 0) \rightarrow 27$$ - also good mapping, output 0x11011 still has $$123$$ leading zeros
• $$(2^{30}, 2^{15}) \rightarrow 2^{43}$$ - good mapping, sum of arguments zeros is $$33 + 48 = 81$$ which is close enough to output's $$84$$
• $$(0, 0) \rightarrow 2^{50}$$ - bad mapping, only $$77$$ zeros in the output
• $$f(a,b) = a × b$$ preserves zero sum well but is not a perfect hash function
1. It's fine if the function doesn't work well with a small subset of arguments: $$1\%$$ of all pairs violates weak zero sum preservation is acceptable, but the function still should be a perfect hash function.
2. The function should not use additional memory like lookup tables.
3. If $$z(x)$$ is the number of leading bits then zero sum is $$N$$-preserved if $$| z(x) + z(y) - z(f(x,y))| \leq N$$, I'm looking for $$N \leq 3$$, but $$N \leq 6$$ are good enough.
• How is $27$ a good mapping for $(0, 0)$ since it does not have $128$ leading zeros? Commented Nov 25, 2022 at 13:27
• I don't need a precise zero sum preservation Commented Nov 25, 2022 at 13:37
• This is very unclear what you consider good or bad. Please be more precise in your post. Commented Nov 25, 2022 at 13:40
• added exact requirement Commented Nov 25, 2022 at 13:44
• What is $\text{bsr}$ ?
– user16034
Commented Nov 25, 2022 at 17:18

Consider the sequence $$S$$ which enumerates pairs $$\langle s,t \rangle$$ of 64-bit strings, with the following ordering:

• If $$z(s)+z(t) < z(s')+z(t')$$, then $$\langle s,t \rangle$$ is listed before $$\langle s',t' \rangle$$.

• If $$z(s)+z(t) = z(s')+z(t')$$ and $$z(s) < z(s')$$, then $$\langle s,t \rangle$$ is listed before $$\langle s',t' \rangle$$.

• If $$z(s)=z(s')$$ and $$z(t)=z(t')$$ and the concatenation $$s\, t$$ comes lexicographically before the concatenation $$s' \, t'$$, then $$\langle s,t \rangle$$ is listed before $$\langle s',t' \rangle$$.

Consider the sequence $$T$$ which enumerates 128-bit strings $$u$$, with the following ordering:

• If $$z(u) < z(u')$$, then $$u$$ is listed before $$u'$$.

• If $$z(u)=z(u')$$ and $$u$$ comes lexicographically before $$u'$$, then $$u$$ is listed before $$u'$$.

Now consider the mapping that maps from a pair $$\langle s,t \rangle$$ to its index in $$S$$, call the result $$i$$, then finds the $$i$$th item in $$T$$, and outputs the result. This then is a perfect hash function, and I believe it satisfies your desired property. Moreover, it is possible to compute both mappings (i.e., the ranking in $$S$$ and unranking in $$T$$) fairly efficiently. Therefore, the hash function can be computed fairly efficiently.