Откуда пришли константы расстояния Хэмминга - PullRequest
Новая
       24

Откуда пришли константы расстояния Хэмминга

1 голос
/ 06 марта 2019

Функция : 

function popcount (x, n) {
  if (n !== undefined) {
    x &= (1 << n) - 1
  }

  x -= x >> 1 & 0x55555555
  x = (x & 0x33333333) + (x >> 2 & 0x33333333)
  x = x + (x >> 4) & 0x0f0f0f0f
  x += x >> 8
  x += x >> 16

  return x & 0x7f
}

Для расчета Вес Хэмминга . Мне интересно, откуда эти константы и как вообще этот метод был открыт. Хотите знать, если кто-нибудь знает ресурс, который описывает его.

1 Ответ

2 голосов
/ 06 марта 2019

Там маски выбирают четные k-битные части, k = 1 дает 0x55555555, k = 2 дает 0x33333333, k = 4 дает 0x0f0f0f0f.

В двоичном коде маски выглядят следующим образом: 

0x55555555 = 01010101010101010101010101010101
0x33333333 = 00110011001100110011001100110011
0x0f0f0f0f = 00001111000011110000111100001111

Они также являются результатом 0xffffffff / 3, 0xffffffff / 5 и 0xffffffff / 17, но это арифметическое понимание, вероятно, не полезно в этом контексте.

В целом этот метод вычисления веса Хэмминга имеет виддерева, в котором первые смежные биты суммируются в 2-битное число, затем смежные 2-битные числа суммируются в 4-битные числа и т. д.

Все шаги могут иметь такую ​​форму: 

x = (x & m[k]) + ((x >> k) & m[k])

, где m[k] - маска, выбирающая четные k-битные части.

Но для многих шагов доступны короткие пути.Например, для суммирования смежных битов нужно рассмотреть только 4 случая: 

00 -> 00
01 -> 01
10 -> 01
11 -> 10

Это можно сделать, извлекая оба бита и суммируя их, но x -= x >> 1 & 0x55555555 также работает.Это вычитает старший бит из 2-битной части, так что 

00 -> 00 - 0 = 00
01 -> 01 - 0 = 01
10 -> 10 - 1 = 01
11 -> 11 - 1 = 10

Может быть, это можно обнаружить с помощью "сообразительности и проницательности", какими бы они ни были.

На шаге x = (x + (x >> 4)) & 0x0f0f0f0f(дополнительные скобки добавлены для ясности), используется пара свойств.Результатами предыдущих шагов являются веса Хэмминга 4-битных строк, хранящихся в 4 битах каждая, поэтому они не более 0100. Это означает, что два из них могут быть добавлены на месте без переноса в следующую более высокую часть, поскольку их суммабудет самое большее 1000, который все еще подходит.Таким образом, вместо того, чтобы маскировать дважды перед суммой, достаточно маскировать один раз после суммы, эта маска эффективно расширяет четные 4-битные части на 8-битные.Это может быть обнаружено при рассмотрении максимальных значений на каждом шаге.

Шаг x += x >> 8 имеет аналогичные рассуждения, но он работает еще лучше, даже маскирование после суммы не требуется, это оставляет некоторые "случайные биты"во втором байте снизу и в верхнем байте, но это не повредит следующему шагу: >> 16 выбрасывает второй байт снизу, в конце все биты-биты удаляются с помощью x & 0x7f.

...