Эффективный бит переназначения алгоритм

Question

У меня есть случай использования, где нужно карабкаться вход таким образом, что:

1. Каждый конкретный вход всегда отображается на определенной псевдослучайной выходе.
2. Выход должен перемешать вход достаточно, чтобы приращающийся вход отображался на псевдослучайный выход.

Например, если входной бит 64 бит, то должно быть ровно 2^64 уникальных выхода, и они должны как можно более прерывать вложенные входы (произвольное требование).

Я буду указывать это на C#, но может переводить с Java или C, если нет встроенных SIMD-интерфейсов. То, что я ищу, - это уже существующий код, а не изобретать колесо.

Я просмотрел Google, но не нашел ничего, что делает сопоставление 1: 1.

Answer 1

Это, кажется, работает довольно хорошо:

const long multiplier = 6364136223846793005; 
const long mulinv_multiplier = -4568919932995229531; 
const long offset = 1442695040888963407; 

static long Forward(long x) 
{ 
    return x * multiplier + offset; 
} 

static long Reverse(long x) 
{ 
    return (x - offset) * mulinv_multiplier; 
} 

Вы можете изменить константы на то, что до тех пор, как multiplier нечетно и mulinv_multiplier является модульным мультипликативным обратный (см. wiki:modular multiplicative inverse или Хакеры Delight 10-15 Точное разделение константами) multiplier (по модулю 2^64, очевидно - и поэтому multiplier должен быть нечетным, иначе он не имеет обратного).

Смещение может быть любым, но сделать его относительно простым с 2^64, чтобы быть в безопасности.

Эти конкретные константы исходят из линейного конгруэнтного генератора Кнута.

Есть одна небольшая вещь: она помещает дополнение LSB ввода в LSB результата. Если это проблема, вы можете просто повернуть ее на любую ненулевую сумму.

---

Для 32 бит, константы могут быть multiplier = 0x4c957f2d, offset = 0xf767814f, mulinv_multiplier = 0x329e28a5.

Для 64 бит multiplier = 12790229573962758597, mulinv_multiplier = 16500474117902441741 может работать лучше.

---

Или вы могли бы использовать CRC, который reversible для такого использования (т.е. вход имеет тот же размер, как CRC) для CRC64 это требует некоторых модификаций конечно.

Answer 2

Просто из верхней части моей головы:

1. Сдвиг вход: Убедитесь, что вы держите каждый бит, т.е. использовать две операции сдвига в различных направлениях и OR результат вместе.

2. Применить статический XOR.

Все остальное, что приходит мне на ум, не будет биективным. Тем не менее, поиск Биективного может принести что-то полезное; D