Как упаковать в 128 бит значения?

Question

[Сергей Соколов]

Порядок 32 элементов хочется задать всего 128-ю битами. «Почти» получается.

Положение 0-го это одна из 32 позиций от 0-й до 31-й, потребуется 5 бит.
Положение 1-го одна из 31 оставшихся, 0..30, 5 бит.
...
15: 1 из 16, тоже 5 бит.
Итого уже 16 * 5 = 80 бит.
16: 1 из 15 позиций, уже всего 4 бита.
...
24: 1 из 8, 4 бита.
Итого 80 + 4 * 8 = 112 бит использовано.
25: 1 из 7, 3 бита.
...
28: 1 из 4, 3 бита.
Итого 112 + 3 * 4 = 124
29: 1 из 3, 2 бита.
30: 1 из 2, 2 бита.
Итого 124 + 4 = 128 бит.

Не хватает 1 бита, чтобы на 31-м шаге выбрать один из двух вариантов.

Можно ли как-то изменить схему и таки поместить в 128 бит вариант перемешивания 32 элементов?

Обратная операция по получению из 128 бит массива уникальных целых 0..31 не должна требовать квантовых вычислений, разумеется.

Answer 1

[longclaps]

Не надо гранулировать то, чего не надо гранулировать.

2^128 = 340282366920938463463374607431768211456
  32! =    263130836933693530167218012160000000

А если очень хочется - можно слить 2 неудобных сомножителя в 1 удобный, напр

25*5 = 125 < 128
 или
 5*3       <  16

и кодировать позиции 25го с конца (те 8 по твоему счету) бита и 5го семью битами.
Я не проверял, но, наверное, влезет.

Comments

[Сергей Соколов]

Развернуть длинное целое, идентифицирующее вариант, в массив 32 уникальных позиций 0..31 – та ещё задача факторизации )

[longclaps]

Сергей Соколов, хех, ответ прочитал - нифига не понял )))
Смотри, ты можешь кодировать в основном по своей схеме, но с исключениями, например, удобно кодировать 2 позиции вида 2^n-1 и 2^n+1 одним числом разрядности 2n - на этом экономится 1бит. Напр 3 и 5 по отдельности кодируется в 2+3 бита, а вместе - 4бита.
Развернуть короткое целое сможешь? )

[Сергей Соколов]

longclaps, о, точно!

2^n-1 и 2^n+1 одним числом разрядности 2n

– то, что надо! Обнимаю и жму руку.

[Сергей Соколов]

про «развернуть длинное целое» я имел в виду, что не понял как из числа порядка 32! получить закодированный им порядок 32 элементов.

Answer 2

[Rsa97]

Берём номер первого элемента (0..31)
Умножаем на 31, прибавляем номер второго элемента в последовательности с удалённым первым элементом (0..30).
Умножаем на 30, прибавляем номер третьего элемента в последовательности с удалёнными первым и вторым элементами (0..29).
...
Умножаем на 2, прибавляем номер тридцать первого элемента в последовательности с удалёнными первым - тридцатым элементами (0..1).
Максимум получим 8.68331761881189e+36, что меньше 2¹²⁸ = 3.4028237e+38.

Comments

[Сергей Соколов]

Обратное преобразование вызывает мучительные размышления

[Rsa97]

Сергей Соколов, Обратным ходом.
Делим на 2, остаток - номер 31 элемента.
Частное делим на 3, остаток - номер 30 элемента.
...
Частное делим на 31, остаток - номер 2 элемента.
Частное - номер 1 элемента.
Да, понадобится длинная арифметика.

[Сергей Соколов]

Да, вариант! Спасибо!
Из-за требования к длинной арифметике не смогу использовать в нынешней задаче, к сожалению.