Comprimindo dois números inteiros sem considerar a ordem

20

Comparando um par ordenado (x, y) a um par não ordenado {x, y} (conjunto) e, em seguida, informações teoricamente, a diferença é de apenas um bit, pois se x vem primeiro ou y requer exatamente um único bit para representar.

Portanto, se recebermos um conjunto {x, y} em que x, y são dois números inteiros de 32 bits diferentes, podemos agrupá-los em 63 bits (em vez de 64)? Deve ser possível recuperar os números inteiros originais de 32 bits a partir do resultado de 63 bits, mas sem conseguir recuperar a ordem deles.

Troy McClure
fonte

Respostas:

27

Sim, pode-se. Se , mapeie o conjunto para o número{ x , y }x<y{x,y}

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

É fácil mostrar que é bijetivo e, portanto, isso pode ser decodificado exclusivamente. Além disso, quando , temos , então isso mapeia o conjunto para um número de 63 bits f (x, y) . Para decodificar, você pode usar a pesquisa binária em y ou obter uma raiz quadrada: y deve ser aproximadamente \ lfloor \ sqrt {2 f (x, y)} \ rfloor .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
fonte
1
assim como 1 + 2 + 3 + ... + y + x legal!
Troy McClure
1
alguma generalização para n ints não ordenados? :) pensando bem, muitas quadforms com derivadas parciais suficientemente grandes vai fazer o trabalho
Troy McClure
4
Outra resposta que pode ser atraente por seu baixo custo de computação: se xe yfor diferente, então um x-y-1ou y-x-1(ambos mod , é claro) cabe em 31 bits. Se for pequeno, concatene e os últimos 31 bits de ; caso contrário, concatenar e os últimos 31 bits de . Recupere os dois números, tomando os primeiros 32 bits como um número e adicionando os primeiros 32 bits, os últimos 31 bits e a constante 1 (mod ) como o outro. 2 32232x-y-1yx-y-1xy-x-1232
Daniel Wagner
1
o método também generalizar muito bem para adicionar mais números, como o primeiro número é "apenas lá" para cadeia de lata
Troy McClure
4
@DW: Você também pode adicionar como criou essa representação? Caso contrário, parece que você o tirou do nada.
Mehrdad 10/05
9

Como uma adição à resposta da DW, observe que este é um caso particular do Sistema Combinatório de Números , que mapeia compactamente uma sequência estritamente decrescente de números inteiros não negativos para kck>>c1

N=i=1k(cii).

Este número tem uma interpretação simples. Se ordenarmos essas sequências lexicograficamente, conta o número de sequências menores.N

Para decodificar, apenas atribua a o maior valor, de modo que e decodifique como uma sequência .ck(ckk)NN(ckk)(k1)

filipos
fonte
4

O número total de pares de números não ordenados em um conjunto de é . O número total de pares não ordenados de números distintos é . São necessários bits para representar um par ordenado de números e, se você tiver um bit a menos, poderá representar elementos de um espaço de até . O número de pares não ordenados não necessariamente distintos é um pouco mais da metade do número de pares ordenados, portanto você não pode economizar um pouco na representação; o número de pares distintos não ordenados é um pouco menos da metade, para que você possa economizar um pouco.NN(N+1)/2N(N1)/22log2(N)=log2(N2)N2/2

Para um esquema prático fácil de calcular, com sendo uma potência de 2, você pode trabalhar na representação bit a bit. Tome que é o operador XOR (exclusivo bit a bit ou). O par pode ser recuperado de ou . Agora, procuraremos um truque para economizar um bit na segunda parte e atribuir uma função simétrica a e para que o pedido não possa ser recuperado. Dado o cálculo da cardinalidade acima, sabemos que esse esquema não funcionará no caso em que .Na=xy{x,y}(a,x)(a,y)xyx=y

Se , há alguma posição de bit onde eles diferem. Escreverei para o ésimo bit de (ie ) e da mesma forma para . Seja a menor posição de bit onde e diferem: é a menor tal que . é o menor tal que : podemos recuperar de . Seja ou ouxyxiixx=ixi2iykxykixiyikiai=1kabxycom o bit apagado (ou seja, ou ) - para tornar a construção simétrica, escolha se e e escolha se e . Use como a representação compacta do par. O par original pode ser recuperado calculando o bit de ordem mais baixa definido em , inserindo um bit 0 nesta posição em (produzindo um de ou ) e levando o xor desse número comkb=i<kxi2i+i>kxi2i1b=i<kyi2i+i>kyi2i1xxk=0yk=1yxk=1yk=0(a,b)abxya (produzindo o outro elemento do par).

Nesta representação,a pode ser qualquer número diferente de zero pode ser qualquer número com metade do intervalo. Esta é uma verificação de sanidade: obtemos exatamente o número esperado de representações de pares não ordenados.b

Em pseudocódigo, com ^, &, |, <<, >>, ~sendo C-como operadores de bits (XOR, e, ou, desvio para a esquerda, direita-shift, 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- parar de ser mau'
fonte
0

Uma prova não construtiva: existem pares não ordenados de diferentes números inteiros de 32 bits.(232×232232)/2=231(2321)<263

Martín-Blas Pérez Pinilla
fonte