Сравнивая упорядоченную пару (x, y) с неупорядоченной парой {x, y} (set), затем теоретически определяем, что разница составляет всего один бит, так как x идет первым или y требуется ровно один бит для представления.
Итак, если нам дан набор {x, y}, где x, y - два разных 32-разрядных целых числа, можем ли мы упаковать их в 63 бита (точнее, в 64)? Должна быть возможность восстановить исходные 32-битные целые числа из 63-битного результата, но без возможности восстановить их порядок.
источник
x
иy
отличаются, то либоx-y-1
илиy-x-1
(оба мода , конечно) умещается в 31 бит. Если мало, то конкатенация и последние 31 бит ; иначе конкатенация и последние 31 бит . Восстановите два числа, взяв первые 32 бита как одно число и добавив первые 32 бита, последние 31 бит и константу 1 (mod ) в качестве другого. 2 32x-y-1
y
x-y-1
x
y-x-1
В дополнение к ответу DW обратите внимание, что это частный случай Комбинаторной системы счисления , которая компактно отображает строго убывающую последовательность неотрицательных целых чисел в c k > ⋯ > c 1 N = k ∑ i = 1 ( c ik ck>⋯>c1
Это число имеет простую интерпретацию. Если мы упорядочим эти последовательности лексикографически, то подсчитывает количество меньших последовательностей.N
Для декодирования просто присвойте наибольшее значение, такое что и декодируйте как -последовательность.( с кck N- ( ck(ckk)≤N (k-1)N−(ckk) (k−1)
источник
Общее количество неупорядоченных пар чисел в наборе из равно . Общее количество неупорядоченных пар различных чисел равно . Для представления упорядоченной пары чисел требуется битов, и, если у вас на один бит меньше, вы можете представить элементы пространства до . Количество неупорядоченных не обязательно различимых пар немного больше половины количества упорядоченных пар, поэтому вы не можете сохранить бит в представлении; количество неупорядоченных пар немного меньше половины, поэтому вы можете немного сэкономить.N ( N + 1 ) / 2 N ( N - 1 ) / 2 2 лог 2 ( Н ) = войти 2 ( N 2 ) N 2 / 2N N(N+1)/2 N(N−1)/2 2log2(N)=log2(N2) N2/2
Для практической схемы, которую легко вычислить, так как является степенью 2, вы можете работать с побитовым представлением. Возьмем где - оператор XOR (побитовый исключающий или). Пара может быть восстановлена из или . Теперь мы будем искать хитрость для сохранения одного бита во второй части и придания симметричной роли и чтобы порядок не мог быть восстановлен. Учитывая приведенное выше вычисление мощности, мы знаем, что эта схема не будет работать в случае, когда .a = x ⊕ y ⊕ { x , y } ( a , x ) ( a , y ) x y x = yN a=x⊕y ⊕ {x,y} (a,x) (a,y) x y x=y
Если то есть битовая позиция, в которой они отличаются. Я напишу для го бита (то есть ), а также для . Пусть займет позицию наименьшего бита, где и различаются: - наименьшее такое что . является наименьшим таким, что : мы можем восстановить из . Пусть будет либо либоx≠y xi i x x=∑ixi2i y k x y k i xi≠yi k i ai=1 k a b x y со стертым битом (т. е. или ) - чтобы сделать конструкцию симметричной, выберите если и , и выберите если и . Используйте в качестве компактного представления пары. Исходная пара может быть восстановлена путем вычисления бита самого младшего порядка, который установлен в , вставки 0 битов в этой позиции в (с получением одного из или ) и взятия xor этого числа с помощьюk b=∑i<kxi2i+∑i>kxi2i−1 b=∑i<kyi2i+∑i>kyi2i−1 x xk=0 yk=1 y xk=1 yk=0 (a,b) a b x y a (получая другой элемент пары).
В этом представлении может быть любым ненулевым числом, а может быть любым числом с половиной диапазона. Это проверка работоспособности: мы получаем именно ожидаемое количество представлений неупорядоченных пар.a b
В псевдокоде, с
^
,&
,|
,<<
,>>
, представляют~
собой С-подобных операторов поразрядными (XOR, и, или, сдвига влево, сдвига вправо, дополнение):источник
Неконструктивное доказательство: имеется неупорядоченных пары разных 32-битных целых чисел.(232×232−232)/2=231(232−1)<263
источник