Bit interleaving seems to be the best solution. The two original numbers can be easily decoded in constant time.
(see http://mathworld.wolfram.com/PairingFunction.html, and Pigeon, P. Contributions à la compression de données. Ph.D. thesis. Montreal, Université de Montréal, 2001. page 115)