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

Порядок 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 не должна требовать квантовых вычислений, разумеется.
  • Вопрос задан
  • 217 просмотров
Решения вопроса 2
longclaps
@longclaps
Не надо гранулировать то, чего не надо гранулировать.
2^128 = 340282366920938463463374607431768211456
  32! =    263130836933693530167218012160000000

А если очень хочется - можно слить 2 неудобных сомножителя в 1 удобный, напр
25*5 = 125 < 128
 или
 5*3       <  16

и кодировать позиции 25го с конца (те 8 по твоему счету) бита и 5го семью битами.
Я не проверял, но, наверное, влезет.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Берём номер первого элемента (0..31)
Умножаем на 31, прибавляем номер второго элемента в последовательности с удалённым первым элементом (0..30).
Умножаем на 30, прибавляем номер третьего элемента в последовательности с удалёнными первым и вторым элементами (0..29).
...
Умножаем на 2, прибавляем номер тридцать первого элемента в последовательности с удалёнными первым - тридцатым элементами (0..1).
Максимум получим 8.68331761881189e+36, что меньше 2128 = 3.4028237e+38.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы