Pseudo-random-looking one-to-one int32->int32 function

Question

I am looking for a int32->int32 function that is

bijection (one-to-one correspondence)
cheap to calculate at least in one direction
transforms the increasing sequence 0, 1, 2, 3, ... into a sequence looking like a good pseudo-random sequence (~ half bits flip when argument changes by a small number, no obvious patterns)

Similar question: [Obfuscating an ID](http://stackoverflow.com/q/8554286/1009831). — Evgeny Kluev, Mar 20 '13 at 20:27
How cheap is "cheap"? Any reasonable block cipher should offer your pseudo-random/bit flip desire. — Jason Malinowski, Mar 20 '13 at 20:28

score 10 · Accepted Answer · answered Mar 20 '13 at 20:29

Multiply by a large odd number and xor with a different one.

Bijection: odd numbers have a multiplicative inverse modulo powers of two, so the multiplication is undone by a multiplication by the inverse. And xor is, of course, undone by another xor.

This is basically how the linear congruence pseudo random number generator works.

score 3 · Answer 2 · answered Mar 20 '13 at 21:19

Probably an overkill for this task, but have you consider applying any crypto pseudo random permutation or other primitives comes from block ciphers. For example, it may be done using des with known key in counter mode:

younumber xor (des (key, number counter))

Pseudo-random-looking one-to-one int32->int32 function

2 Answers2

Linked