Comprimir dos enteros sin tener en cuenta el orden

20

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.

Troy McClure
fuente

Respuestas:

27

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

f(x,y)=y(y1)/2+x.

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 f0x<y<2320f(x,y)<263231{x,y}f(x,y)yy2f(x,y)

DW
fuente
1
al igual que 1 + 2 + 3 + ... + y + x agradable!
Troy McClure
1
¿Alguna generalización a n entradas desordenadas? :) pensándolo bien, muchos quadforms con derivados parciales suficientemente grandes harán el trabajo
Troy McClure
44
Otra respuesta que puede ser atractiva por su bajo costo de cálculo: si xy yson diferentes, entonces cualquiera x-y-1o y-x-1(ambos mod , por supuesto) cabe en 31 bits. Si es pequeño, concatene y los últimos 31 bits de ; de lo contrario concatenar y los últimos 31 bits de . Recupere los dos números tomando los primeros 32 bits como un número y sumando los primeros 32 bits, los últimos 31 bits y la constante 1 (mod ) como el otro. 2 32232x-y-1yx-y-1xy-x-1232
Daniel Wagner
1
su método también se generaliza bien para sumar más números, ya que el primer número está "justo ahí", así que puede encadenar
Troy McClure
44
@DW: ¿Podría agregar también cómo se le ocurrió esta representación? De lo contrario, parece que lo sacaste de la nada.
Mehrdad
9

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 ikck>>c1

N=i=1k(cii).

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 kckN- ( ck(ckk)N (k-1)N(ckk)(k1)

filipos
fuente
4

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 )NN(N+1)/2N(N1)/22log2(N)=log2(N2)N2/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 yNa=xy{x,y}(a,x)(a,y)xyx=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 iy 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 yxyxiixx=ixi2iykxykixiyikiunyo=1kunsiXycon 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 conk b=si=yo<kXyo2yo+yo>kXyo2yo-1 x x k = 0 y k = 1 y x k = 1 y k = 0 ( a , b ) a b xsi=yo<kyyo2yo+yo>kyyo2yo-1XXk=0 0yk=1yXk=1yk=0 0(un,si)unsiXayun (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.bunsi

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)
Gilles 'SO- deja de ser malvado'
fuente
0

Una prueba no constructiva: hay sin ordenar pares de diferentes enteros de 32 bits.(232×232-232)/ /2=231(232-1)<263

Martín-Blas Pérez Pinilla
fuente