Блог

Функция:

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

  x -= x >> 1 amp; 0x55555555
  x = (x amp; 0x33333333)   (x >> 2 amp; 0x33333333)
  x = x   (x >> 4) amp; 0x0f0f0f0f
  x  = x >> 8
  x  = x >> 16

  return x amp; 0x7f
}
  

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

Там маски выбирают четные 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 amp; m[k])   ((x >> k) amp; m[k])
  

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

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

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

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

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

Возможно, это можно было бы обнаружить с помощью «сообразительности и проницательности», что бы это ни было.

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

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