Сжатие двух целых чисел без учета порядка

20

Сравнивая упорядоченную пару (x, y) с неупорядоченной парой {x, y} (set), затем теоретически определяем, что разница составляет всего один бит, так как x идет первым или y требуется ровно один бит для представления.

Итак, если нам дан набор {x, y}, где x, y - два разных 32-разрядных целых числа, можем ли мы упаковать их в 63 бита (точнее, в 64)? Должна быть возможность восстановить исходные 32-битные целые числа из 63-битного результата, но без возможности восстановить их порядок.

Трой МакКлюр
источник

Ответы:

27

Да, можно. Если , сопоставьте множество с числомx<y{x,y}

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

Легко показать, что биективен, и поэтому он может быть уникально декодирован. Кроме того, когда , мы имеем , поэтому это отображает множество до 63-битного числа . Для декодирования вы можете использовать бинарный поиск по или взять квадратный корень: должно быть примерно .f0x<y<2320f(x,y)<263231{x,y}f(x,y)yy2f(x,y)

DW
источник
1
просто как 1 + 2 + 3 + ... + у + х приятно!
Трой МакКлюр
1
какое-то обобщение неупорядоченных целых? :) если подумать, многие квадратные формы с достаточно большими частными производными сделают эту работу
Трой МакКлюр
4
Другой ответ, который может быть привлекательным из-за его низкой стоимости вычислений: если xи yотличаются, то либо x-y-1или y-x-1(оба мода , конечно) умещается в 31 бит. Если мало, то конкатенация и последние 31 бит ; иначе конкатенация и последние 31 бит . Восстановите два числа, взяв первые 32 бита как одно число и добавив первые 32 бита, последние 31 бит и константу 1 (mod ) в качестве другого. 2 32232x-y-1yx-y-1xy-x-1232
Даниэль Вагнер
1
Ваш метод также хорошо подходит для добавления большего числа чисел, так как первое число «просто есть», так что можно цепочку
Трой МакКлюр
4
@DW: Не могли бы вы также добавить, как вы пришли к этому представлению? В противном случае кажется, что вы вытащили его из воздуха.
Мердад
9

В дополнение к ответу DW обратите внимание, что это частный случай Комбинаторной системы счисления , которая компактно отображает строго убывающую последовательность неотрицательных целых чисел в c k > > c 1 N = k i = 1 ( c ikck>>c1

N=i=1k(cii).

Это число имеет простую интерпретацию. Если мы упорядочим эти последовательности лексикографически, то подсчитывает количество меньших последовательностей.N

Для декодирования просто присвойте наибольшее значение, такое что и декодируйте как -последовательность.( с кckN- ( ck(ckk)N (k-1)N(ckk)(k1)

Filipos
источник
4

Общее количество неупорядоченных пар чисел в наборе из равно . Общее количество неупорядоченных пар различных чисел равно . Для представления упорядоченной пары чисел требуется битов, и, если у вас на один бит меньше, вы можете представить элементы пространства до . Количество неупорядоченных не обязательно различимых пар немного больше половины количества упорядоченных пар, поэтому вы не можете сохранить бит в представлении; количество неупорядоченных пар немного меньше половины, поэтому вы можете немного сэкономить.N ( N + 1 ) / 2 N ( N - 1 ) / 2 2 лог 2 ( Н ) = войти 2 ( N 2 ) N 2 / 2NN(N+1)/2N(N1)/22log2(N)=log2(N2)N2/2

Для практической схемы, которую легко вычислить, так как является степенью 2, вы можете работать с побитовым представлением. Возьмем где - оператор XOR (побитовый исключающий или). Пара может быть восстановлена ​​из или . Теперь мы будем искать хитрость для сохранения одного бита во второй части и придания симметричной роли и чтобы порядок не мог быть восстановлен. Учитывая приведенное выше вычисление мощности, мы знаем, что эта схема не будет работать в случае, когда .a = x y { x , y } ( a , x ) ( a , y ) x y x = yNa=xy{x,y}(a,x)(a,y)xyx=y

Если то есть битовая позиция, в которой они отличаются. Я напишу для го бита (то есть ), а также для . Пусть займет позицию наименьшего бита, где и различаются: - наименьшее такое что . является наименьшим таким, что : мы можем восстановить из . Пусть будет либо либоxyxiixx=ixi2iykxykixiyikiai=1kabxyсо стертым битом (т. е. или ) - чтобы сделать конструкцию симметричной, выберите если и , и выберите если и . Используйте в качестве компактного представления пары. Исходная пара может быть восстановлена ​​путем вычисления бита самого младшего порядка, который установлен в , вставки 0 битов в этой позиции в (с получением одного из или ) и взятия xor этого числа с помощьюkb=i<kxi2i+i>kxi2i1b=i<kyi2i+i>kyi2i1xxk=0yk=1yxk=1yk=0(a,b)abxya(получая другой элемент пары).

В этом представлении может быть любым ненулевым числом, а может быть любым числом с половиной диапазона. Это проверка работоспособности: мы получаем именно ожидаемое количество представлений неупорядоченных пар.ab

В псевдокоде, с ^, &, |, <<, >>, представляют ~собой С-подобных операторов поразрядными (XOR, и, или, сдвига влево, сдвига вправо, дополнение):

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)
Жиль "ТАК - перестань быть злым"
источник
0

Неконструктивное доказательство: имеется неупорядоченных пары разных 32-битных целых чисел.(232×232232)/2=231(2321)<263

Мартин-Блас Перес Пинилья
источник