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)