Ключом к максимальному сохранению энтропии некоторого исходного 32-битного «сигнала» является обеспечение того, чтобы каждый из 32 входных битов имел независимую и равную способность изменятьзначение 16-разрядного выходного слова.
Поскольку OP запрашивает размер в битах, равный половине исходного размера, самый простой способ удовлетворить этот критерий - XOR .верхняя и нижняя половины, как уже упоминалось.Использование XOR является оптимальным, поскольку - как и очевидно по определению XOR - независимое переключение любого из 32 входных битов гарантированно изменит значение16-битный вывод.
Проблема становится более интересной, когда вам необходимо дальнейшее уменьшение, помимо половины размера , скажем, от 32-битного входа до,скажем, 2-битный вывод .Помните, цель состоит в том, чтобы сохранить как можно больше энтропии от источника, поэтому решения, которые включают в себя наивное маскирование двух младших битов с (i & 3), как правило, движутся в неправильном направлении;выполнение этого гарантирует , что никакие биты не могут быть обработаны, кроме немаскированных битов, влияющих на результат, и это обычно означает, что есть произвольная, возможно, полезная часть сигнала времени выполнения, которая суммируетсяотбрасывается без принципа.
Исходя из предыдущего параграфа, вы, конечно, могли бы выполнить итерацию с XOR три раза, чтобы получить 2-битный выход с желаемым свойством равного влияния каждым / любым из входных битов.Конечно, это решение по-прежнему оптимально правильно, но включает циклы или несколько развернутых операций, которые, как оказывается, не нужны!
К счастью, есть хорошая техника, состоящая из двух операций , которая дает доказуемо-оптимальный результат для этогоситуация.Как и в случае XOR , он не только гарантирует, что при любом заданном 32-разрядном значении изменение любого одного из входных битов приведет к изменению (например) 2-разрядного выходного значения, но также и в том, чтораспределение 2-битных выходных значений совершенно равномерно.Другими словами, над 4,294,967,296 возможными входными значениями будет точно 1,073,741,824 каждого из четырех возможных 2-битных результатов хеширования { 0, 1, 2, 3 }.
В методе, который я здесь упоминаю, используются определенные магические значениякоторый я обнаружил с помощью исчерпывающего поиска, и который, кажется, не обсуждается в других местах в Интернете, по крайней мере, для конкретного обсуждаемого здесь использования (т. е. обеспечения равномерного распределения хешей, максимально сохраняющего энтропию).Любопытно, что в соответствии с этим же исчерпывающим поиском магические значения на самом деле уникальны. Это означает, что для каждой целевой ширины в битах { 16, 8, 4, 2 } магическое значение, которое я показываю ниже, является только значение, которое при использовании, как я покажу здесь, удовлетворяет идеальным критериям хэширования, описанным выше.
Без дальнейших церемоний уникальная и математически оптимальная процедура для хеширования 32 битов до n = { 16, 8, 4, 2 } равна умножению по магическому значению, соответствующему n (без знака, отбрасывание переполнения), а затем принять n старшие биты результата.Чтобы выделить эти результирующие биты в качестве значения хеш-функции в диапазоне [0 ... (2ⁿ - 1)], просто сдвиньте вправо (без знака!) Результат умножения на 32 - n бит.
"магические" значения и C-подобный синтаксис выражения выглядит следующим образом:
Максимально сохраняющий энтропию хэш для сокращения с 32-битных до ...
Target Bits Multiplier Right Shift Expression
----------- ------------ ----------- -----------------------
16 0x80008001 16 (i * 0x80008001) >> 16
8 0x80808081 24 (i * 0x80808081) >> 24
4 0x88888889 28 (i * 0x88888889) >> 28
2 0xAAAAAAAB 30 (i * 0xAAAAAAAB) >> 30
Примечания:
- Использовать 32-разрядное умножение без знака и отбрасывать любое переполнение (умножение на 64 бита не требуется).
- При выделении результата с использованием сдвига вправо (как показано) обязательно используйте операцию сдвига без знака .
[ edit: добавлена таблица для 64-битных входных значений]
Максимально сохраняющий энтропию хеш для уменьшения 64-битного значения до ...
Target Bits Multiplier Right Shift Expression
----------- ------------------ ----------- -------------------------------
32 0x8000000080000001 32 (i * 0x8000000080000001) >> 32
16 0x8000800080008001 48 (i * 0x8000800080008001) >> 48
8 0x8080808080808081 56 (i * 0x8080808080808081) >> 56
4 0x8888888888888889 60 (i * 0x8888888888888889) >> 60
2 0xAAAAAAAAAAAAAAAB 62 (i * 0xAAAAAAAAAAAAAAAB) >> 62
Дальнейшее обсуждение
Я нашел все это довольно круто. С практической точки зрения ключевое информационное теоретическое требование - это гарантия того, что для любого входного значения m-bit и соответствующего ему результата хеш-значения n-bit переключение любого из m исходных битов всегда вызывает некоторые изменения в n-bit значении результата . Теперь, хотя всего имеется 2ⁿ возможных значений результата, одно из них уже "используется" , поскольку переключение результата на это значение не изменится вообще. Это оставляет только 2ⁿ - 1 результирующие значения, которые могут быть использованы всем набором m входных значений, созданных одним переворотом.
Давайте рассмотрим пример; на самом деле, чтобы показать, как эта техника может граничить с жутким или совершенно волшебным, мы рассмотрим более экстремальный случай, когда m = 64 и n = 2. С 2 выходными битами возможны четыре значения результата, { 0, 1, 2, 3 }. Предполагая произвольное 64-битное входное значение 0x7521d9318fbdf523, мы получаем его 2-битное хеш-значение 1:
(0x7521d9318fbdf523 * 0xAAAAAAAAAAAAAAAB) >> 62 // result --> '1'
Но этот результат влечет за собой то, что без значения в наборе из 64 значений , где один бит 0x7521d9318fbdf523 равен переключено может иметь то же значение результата . То есть ни один из этих 64 других результатов не может использовать значение 1, и все должны вместо этого использовать либо 0, 2, либо 3. Когда каждое из 2⁶⁴ входных значений эгоистично захватывает одну четверть выходного пространства для себя из 64 своих пиров, существует ли одновременно удовлетворительное решение для всех?
Достаточно, конечно, чтобы показать, что (точно?) Один делает , вот значения хеш-результата, перечисленные по порядку, для входов, которые переворачивают один бит 0x7521d9318fbdf523 (по одному за раз) ), от MSB (позиция 63) до LSB (0).
3 2 0 3 3 3 3 3 3 0 0 0 3 0 3 3 0 3 3 3 0 0 3 3 3 0 0 3 3 0 3 3
0 0 3 0 0 3 0 3 0 0 0 3 0 3 3 3 0 3 0 3 3 3 3 3 3 0 0 0 3 0 0 3 // <-- no '1' values
Как видите, не существует значений 1, что означает, что каждый бит в источнике "как есть" должен влиять на результат (или если вы предпочитаете, состояние de facto каждого бита в 0x7521d9318fbdf523 является существенным , чтобы результат не был "не- 1"). Поскольку независимо от того, какое однобитное изменение вы вносите в 64-битный вход, 2-битное значение результата больше не будет 1.
Имейте в виду, что приведенная выше таблица «пропущенных значений» была выведена из анализа только одного случайно выбранного значения примера 0x7521d9318fbdf523; каждое другое возможное входное значение имеет аналогичную собственную таблицу, каждая из которых до жути пропускает фактическое значение результата своего владельца, но все же каким-то образом является глобально непротиворечивой в своем членстве в наборе. Это свойство по существу соответствует максимальному сохранению доступной энтропии во время задачи (с изначально потерями) уменьшения ширины в битах.
Таким образом, мы видим, что каждое из 2⁶⁴ возможных значений источника независимо накладывает, ровно на 64 других значения источника, ограничение исключения одного из возможных значений результата. Что бросает вызов моей интуиции по этому поводу, так это то, что существуют неописанные квадриллионы этих наборов из 64 членов, каждый из которых также принадлежит к 63 прочим , по-видимому, не связанным наборам бит-твидлинга. И все же, несмотря на эту самую запутанную загадку переплетенных ограничений, тем не менее тривиально использовать одно (я полагаю) разрешение, которое одновременно точно удовлетворяет их всем.
Все это, по-видимому, связано с чем-то, что вы, возможно, заметили в таблицах выше: а именно, я не вижу очевидного способа распространить методику на случай сжатия до результата 1-бит .В этом случае есть только два возможных результирующих значения { 0, 1 }, поэтому, если любое / каждое заданное (например) 64-битное входное значение все еще суммарно исключает его собственный результат из всех 64 его соседей с однобитовым переворачиваниемто, что теперь, по существу, налагает другие , только оставшиеся значения для этих 64. Математическая разбивка, которую мы видим в таблице, кажется, сигнализирует, что одновременный результатв таких условиях мост слишком далеко.
Другими словами, специальная «сохраняющая информацию» характеристика из XOR (то есть ее роскошно надежная гарантия того, что в отличие от И , ИЛИ и т. Д., Это c̲a̲n̲ и w̲i̲l̲l̲ всегда немного меняются), что не удивительно, требует определенных затрат, а именно, крайне необоротного спросадля некоторого количества места локтя - по крайней мере 2 бита - для работы.