31-bit Bijective (Perfect) Hash algorithm

Question

What I need

I need an algorithm that produces a bijective output. I have a 31-bit input and need a pseudo-random 31-bit output.

What I have considered

CRCs are bijective within their bit-width.

I have looked on Google and can find the polynomials for this, but not the tables or algorithm.

Could anyone point me in the right direction?

I need a CRC-31 algorithm using polynomial say 0x737e312b, or any bijective function that will do what I need.

NOTE

I found the following code, but I unfortunately don't have the tools to compile and run it.

Answer 1

For any hash function hash, you can do:

function bijectiveHash31(int val) {
    val &= 0x7FFFFFFF; //make sure it's 31 bits
    for (int i=0; i<5; ++i) {
        // the high bits affect the low bits
        val ^= hash(val>>15) & 32767;
        // rotate bits
        val = ((val&32767)<<16) | ((val>>15)&65535);
    }
    return val;
}

This is a Feistel structure, which forms the basis of many ciphers: https://en.wikipedia.org/wiki/Feistel_cipher

If you need it to be fast and you don't need it to be super good, then this works fine:

function bijectiveHash31(int val) {
    val = ((val*RANDOM_ODD_NUMBER) + RANDOM_NUMBER) & 0x7FFFFFFF;
    val ^= (val>>15);
    val ^= (val>>8);
    return val;
}

In both of these cases, it's not too difficult to figure out how you could undo each elementary operation, which shows that the whole hash is bijective. If you need help establishing that for the multiplication, see https://en.wikipedia.org/wiki/Modular_multiplicative_inverse