I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics:

• $f$ should be bijective
• Both $f$ and $f^{-1}$ should be calculable pretty fast
• $f$ should return a number that has no significant correlation to its input.

The rationale is this:

I want to write a program that operates on data. Some information of the data is stored in a binary search tree where the search key is a symbol of an alphabet. With time, I add further symbols to the alphabet. New symbols simply get the next free number available. Hence, the tree will always have a small bias to smaller keys which causes more rebalancing than I think should be needed.

My idea is to mangle the symbol numbers with $f$ such that they are widely spread over the whole range of $[0,2^{64}-1]$. Since the symbol numbers only matter during input and output which happens only once, applying such a function should not be too expensive.

I thought about one iteration of the Xorshift random number generator, but I don't really know a way to undo it, although it should theoretically be possible.

Does anybody know such a function?
Is this a good idea?

-
I'm not an expert, but perhaps you can use a pseudorandom permutation (see for example the Feistel cipher) –  Vor Nov 14 '12 at 23:40
If you are essentially computing a hash function, why not use hashing? –  vonbrand Jan 28 '13 at 23:18
@vonbrand Hashing is not reversible. See requirement number 2. –  FUZxxl Jan 28 '13 at 23:31
Why does it have to be reversible? What is wrong with making it reversible by lookup? –  vonbrand Jan 29 '13 at 1:25
You can store (f(x),x) as keys. –  adrianN Mar 5 '13 at 16:57

You can use Fibonacci hashing, namely

$\qquad h_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot \frac{\sqrt{5} - 1}{2} \right\rfloor$.

For $k=1,\dots,n$ you get $n$ pairwise-distinct numbers (about) evenly spread in $[0,1]$. By scaling to $[1..M]$ and rounding (down), you get about evenly spread numbers in that interval.

For example, these are $h_F(1), \dots, h_F(200)$ scaled to $[0..10000]$ (left original sequence, right sorted):

This is an instance of what Knuth calls multiplicative hashing. For $w$ the computer's word size, $A$ some integer relatively prime to $w$ and $M$ the number of addresses needed, we use

$\qquad h(k) = \left\lfloor M \left( \bigl( k \cdot \frac{A}{w}\bigr) \mod 1 \right) \right\rfloor$

as hashing function. The above follows with $A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$ (make sure you can compute it with a sufficient precision). While this also works with any other irrational number besides $\phi^{-1}$, it is one of only two numbers that lead to the "most uniformly distributed" numbers.

Find more in The Art of Computer Programming, Volume 3 by Donald Knuth (chapter 6.4 from page 513 in the second edition). In particular you'll find why the resulting numbers are pairwise distinct (at least if $n \ll M$) and how to compute the inverse function if you use natural $A$ and $w$ instead of $\phi^{-1}$.

-
How to calculate $f^{-1}$ efficiently? –  frafl Mar 5 '13 at 15:22
@frafl I hope my edit addresses your concern somewhat. It's clear, though, that these hashing techniques are nor particularly designed to be efficiently invertible. –  Raphael Mar 5 '13 at 17:13
Yes it does, I'll upvote it, however I would not recommend it as the accepted answer. –  frafl Mar 6 '13 at 11:18

For $k$-bit inputs, this function works:

$\mathrm{hash}(n) = (n \bmod 2^{\lceil\frac{k}{2}\rceil})\cdot 2^{\lceil\frac{k}{2}\rceil} + n \,\mathrm{div}\, 2^{\lceil\frac{k}{2}\rceil}$

This is reversible, in that $\mathrm{hash}(\mathrm{hash}(n)) = n$, and has non-sequential pairs $\{n,m\}, n < m$, where $\mathrm{hash}(m) < \mathrm{hash}(n)$. Beware that output and input may correlate, especially if your input is in $\{1,\dots,2^{\lceil\frac{k}{2}\rceil}-1\}$.

-
This looks simple and nice. I'm going to test that one. –  FUZxxl Jan 31 '13 at 8:03
1. Depending on the input, it may produce heavy correlation (up to $1$ for Spearman's $\rho$) 2. This is for 32 bits, not for 64 bits 3. Could you please write this in a language-independent way? –  frafl Mar 5 '13 at 15:19
it's pretty clear! for 64-bit (0x00000000FFFFFFFF) and you should shift(<<) 32 bits. This function is simple, practical and fast enough in practice. –  Reza Mar 5 '13 at 18:36
But why don't you use a permutation of the bits, that does not map every $x \in \{1,\dots,2^{32}-1\}$ to $2^{32}x$? As stated above this clearly violates the correlation condition demanded by the OP. –  frafl Mar 6 '13 at 11:00