Comprimir dos enteros sin tener en cuenta el orden

Comparando un par ordenado (x, y) con un par desordenado {x, y} (conjunto), entonces la información teóricamente, la diferencia es solo un bit, ya que si x viene primero o y requiere exactamente un solo bit para representar.

Entonces, si se nos da un conjunto {x, y} donde x, y son dos enteros diferentes de 32 bits, ¿podemos empaquetarlos en 63 bits (en lugar de 64)? Debería ser posible recuperar los enteros originales de 32 bits del resultado de 63 bits, pero sin poder recuperar su orden.

Sí uno puede. Si , asigna el conjunto al número{ x , y $x<y$$\{x,y\}$

Es fácil demostrar que es biyectivo, por lo que esto puede decodificarse de manera única. Además, cuando , tenemos , por lo que esto asigna el conjunto a un número de 63 bits . Para decodificar, puede usar la búsqueda binaria en , o tomar una raíz cuadrada: debe ser aproximadamente .0 ≤ x < y < 2 32 0 ≤ f ( x , y ) < 2 63 - 2 31 { x , y } f ( x , y ) y y ⌊ $f$$0 \le x < y < 2^{32}$$0 \le f(x,y) < 2^{63} - 2^{31}$$\{x,y\}$$f(x,y)$$y$$y$$\lfloor \sqrt{2 f(x,y)} \rfloor$

Como una adición a la respuesta de DW, tenga en cuenta que este es un caso particular del Sistema de números combinatorios , que mapea de manera compacta una secuencia estrictamente decreciente de enteros no negativos a c k > ⋯ > c 1 N = k ∑ i = 1 ( c $k$$c_k > \cdots > c_1$

Este número tiene una interpretación simple. Si ordenamos estas secuencias lexicográficamente, entonces cuenta el número de secuencias más pequeñas.$N$

Para decodificar, simplemente asigne a el valor más grande tal que y decodifique como una secuencia .( c $c_k$N- ( c$\binom{c_k}{k} \leq N$ (k-1$N - \binom{c_k}{k}$$(k-1)$

El número total de pares de números desordenados en un conjunto de es . El número total de pares desordenados de números distintos es . Se necesitan bits para representar un par ordenado de números, y si tiene un bit menos, puede representar elementos de un espacio de hasta . El número de pares no necesariamente desordenados no ordenados es un poco más de la mitad del número de pares ordenados, por lo que no puede guardar un poco en la representación; el número de pares distintos no ordenados es un poco menos de la mitad, por lo que puede ahorrar un poco.N ( N + 1 ) / 2 N ( N - 1 ) / 2 2 log 2 ( N ) = log 2 ( N 2$N$$N(N+1)/2$$N(N-1)/2$$2 \log_2(N) = \log_2(N^2)$$N^2/2$

Para un esquema práctico que sea fácil de calcular, con siendo una potencia de 2, puede trabajar en la representación bit a bit. Tome donde es el operador XOR (exclusivo a nivel de bit o). El par se puede recuperar de o . Ahora buscaremos un truco para guardar un bit en la segunda parte, y le daremos un rol simétrico a e para que el orden no pueda recuperarse. Dado el cálculo de cardinalidad anterior, sabemos que este esquema no funcionará en el caso donde .a = x ⊕ y ⊕ { x , y } ( a , x ) ( a , y ) x $N$$a = x \oplus y$$\oplus$$\{x,y\}$$(a, x)$$(a, y)$$x$$y$$x=y$

Si entonces hay alguna posición de bit en la que difieren. Escribiré para el ésimo bit de (es decir, ), y lo mismo para . Supongamos que toma la posición de bit más pequeña donde e difieren: es la más pequeña, de modo que . es el más pequeño tal que : podemos recuperar de . Deje ser ox i i x x = ∑ i x i 2 i y k x y k i x i ≠ y i k i a i = 1 k a b x y k b = ∑ i < k x i 2 i + ∑ i > k x i 2 ∑ i < k$x \ne y$$x_i$$i$$x$$x = \sum_i x_i 2^i$$y$$k$$x$$y$$k$$i$$x_i \ne y_i$$k$$i$$a_i = 1$$k$$a$$b$$x$$y$con el bit borrado (es decir, o ) - para hacer que la construcción sea simétrica, seleccione si y , y elija si y . Use como la representación compacta del par. El par original se puede recuperar calculando el bit de orden más bajo que se establece en , insertando un bit 0 en esta posición en (produciendo uno de o ), y tomando el xor de ese número con$k$ b$b = \sum_{i<k} x_i 2^i + \sum_{i>k} x_i 2^{i-1}$ x x k = 0 y k = 1 y x k = 1 y k = 0 ( a , b ) a b $b = \sum_{i<k} y_i 2^i + \sum_{i>k} y_i 2^{i-1}$$x$$x_k=0$$y_k=1$$y$$x_k=1$$y_k=0$$(a,b)$$a$$b$$x$$y$$a$ (produciendo el otro elemento del par).

En esta representación, puede ser cualquier número distinto de cero puede ser cualquier número con la mitad del rango. Este es un control de cordura: obtenemos exactamente el número esperado de representaciones de pares desordenados.$a$$b$

En pseudocódigo, con ^, &, |, <<, >>, ~siendo C-como operadores bit a bit (XOR, AND, OR, izquierda turno, desplazamiento a la derecha, complemento):

encode(x, y) =
  let a = x ^ y
  let k = lowest_set_bit_position(a)
  let low_mask = (1 << k) - 1
  let z = if x & (1 << k) = 0 then x else y
  return (a, (z & low_mask) | (z & ~low_mask) >> 1)
decode(a, b) =
  let k = lowest_set_bit_position(a)
  let low_mask = (1 << k) - 1
  let x = (b & low_mask) | ((b & ~low_mask) << 1)
  return (x, a ^ x)

Una prueba no constructiva: hay sin ordenar pares de diferentes enteros de 32 bits.$(2^{32}\times 2^{32} - 2^{32})/2 = 2^{31}(2^{32}-1)<2^{63}$