patternMajor
Compressing two integers disregarding order
Viewed 0 times
ordertwocompressingintegersdisregarding
Problem
Comparing an ordered pair (x,y) to an unordered pair {x, y} (set), then information theoretically, the difference is only one bit, as whether x comes first or y requires exactly a single bit to represent.
So, if we're given a set {x,y} where x,y are two different 32-bit integers, can we pack them into 63 bits (rather 64)? It should be possible to recover the original 32 bit integers from the 63 bit result, but without being able to recover their order.
So, if we're given a set {x,y} where x,y are two different 32-bit integers, can we pack them into 63 bits (rather 64)? It should be possible to recover the original 32 bit integers from the 63 bit result, but without being able to recover their order.
Solution
Yes, one can. If $x<y$, map the set $\{x,y\}$ to the number
$$f(x,y) = y(y-1)/2 + x.$$
It is easy to show that $f$ is bijective, and so this can be uniquely decoded. Also, when $0 \le x < y < 2^{32}$, we have $0 \le f(x,y) < 2^{63} - 2^{31}$, so this maps the set $\{x,y\}$ to a 63-bit number $f(x,y)$. To decode, you can use binary search on $y$, or take a square root: $y$ should be approximately $\lfloor \sqrt{2 f(x,y)} \rfloor$.
$$f(x,y) = y(y-1)/2 + x.$$
It is easy to show that $f$ is bijective, and so this can be uniquely decoded. Also, when $0 \le x < y < 2^{32}$, we have $0 \le f(x,y) < 2^{63} - 2^{31}$, so this maps the set $\{x,y\}$ to a 63-bit number $f(x,y)$. To decode, you can use binary search on $y$, or take a square root: $y$ should be approximately $\lfloor \sqrt{2 f(x,y)} \rfloor$.
Context
StackExchange Computer Science Q#57262, answer score: 27
Revisions (0)
No revisions yet.