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?

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

2 Answers 2


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):

enter image description here

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}$.

  • 1
    $\begingroup$ How to calculate $f^{-1}$ efficiently? $\endgroup$
    – frafl
    Mar 5, 2013 at 15:22
  • 1
    $\begingroup$ @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. $\endgroup$
    – Raphael
    Mar 5, 2013 at 17:13
  • $\begingroup$ Yes it does, I'll upvote it, however I would not recommend it as the accepted answer. $\endgroup$
    – frafl
    Mar 6, 2013 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\}$.

Ref: Reversible hash function

  • $\begingroup$ This looks simple and nice. I'm going to test that one. $\endgroup$
    – fuz
    Jan 31, 2013 at 8:03
  • 1
    $\begingroup$ 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? $\endgroup$
    – frafl
    Mar 5, 2013 at 15:19
  • $\begingroup$ it's pretty clear! for 64-bit (0x00000000FFFFFFFF) and you should shift(<<) 32 bits. This function is simple, practical and fast enough in practice. $\endgroup$
    – Reza
    Mar 5, 2013 at 18:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – frafl
    Mar 6, 2013 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.