A nice bijection from integers to natural numbers. Mappings exist for rationals -> natural numbers and other countable sets, but may be less practical.
That either doesn’t map to rationals (making 1/1 and 2/2 two different numbers) or not a bijection (0x0000000100000001 and 0x0000000200000002 both map back to 1) and doesn’t work on “the integers”.
Most people just care about having a lossless round-trip conversion, from the source representation to a storage representation and then back to the source representation, not about having every possible bit sequence in the storage representation being valid. Univocally mapping the rationals onto a set of contiguous naturals is extremely tricky, computationally.
> Univocally mapping the rationals onto a set of contiguous naturals is extremely tricky, computationally.
It is not that difficult. https://en.wikipedia.org/wiki/Calkin–Wilf_tree#Stern's_diato... defines fusc(n), a function that’s fairly easy to compute (it is recursively defined, but only requires a recursion depth of the number of bits in the binary presentation of n), with fusc(n)/fusc(n+1) being a mapping from the natural numbers to all positive rational numbers.
“The parent of any rational number can be determined after placing the number into simplest terms, as a fraction a/b for which greatest common divisor of an and b is 1. If a/b < 1, the parent of a/b is a/(b − a); if a/b > 1, the parent of a/b is (a − b)/b.”*
Repeatedly using that procedure, you eventually reach 1, and then have found the path from 1 down to your starting number a/b. if you have that finding the n for which fusc(n)/fusc(n+1) = a/b is trivial.
2/2 is not irreducible, so not an issue. But yes, it does create some waste in the encoding. Not obvious how to fix it, as coprimality is hard to encode for.
