Вес Хэмминга

Вес Хэмминга строки — количество символов, отличных от нулевого символа используемого алфавита. Таким образом, он эквивалентен расстоянию Хэмминга от состоящей только из нулей строки той же длины. В наиболее типичном случае, для заданного набора битов, вес равен количеству битов, установленных в 1, или сумме цифр двоичного представления заданного числа и ℓ₁ норме битового вектора.

+ПримерыСтрокаВес Хэмминга11101411101000400000000067801234056710

История и использование Вес Хэмминга назван именем американского математика Ричарда Уэсли Хэмминга, хотя он и не является автором этого понятия. Вес Хэмминга двоичных чисел использовался уже в 1899 году Джеймсом У. Ли Глейшером для формулы числа нечётных биномиальных коэффициентов в одной строке треугольника Паскаля . Ирвинг С. Рид ввёл понятие, эквивалентное весу Хэмминга для бинарного случая, в 1954 году.

Вес Хэмминга используется в некоторых дисциплинах, включая теорию информации, теорию кодирования и криптографию. Примеры приложений веса Хэмминга включают: В алгоритме модульного быстрого возведения в степень, число модульных умножений, требуемых для степени n, равно log2 n + вес(n). Именно поэтому в качестве публичного ключа n, используемого в RSA, обычно выбирается число с низким весом Хэмминга. Вес Хэмминга определяет длины путей между узлами в . Поиск радужной оболочки глаза в биометрических базах данных обычно реализуется путём вычисления расстояния Хэмминга для каждой записи. В программах компьютерных шахмат, использующих представление , вес Хэмминга битовой карты указывает количество оставшихся фигур определённого типа или количество клеток доски, контролируемых фигурами одного игрока, и поэтому является важным фактором, влияющим на оценку позиции. Вес Хэмминга может быть использован для эффективного нахождения используя равенство ffs(x) = pop(x ^ (x - 1)). Это полезно на платформах, таких как SPARC, которые имеют аппаратные инструкции для подсчёта веса Хэмминга, но не имеют аппаратной инструкции для поиска первого установленного бита. Операция вычисления веса Хэмминга может быть интерпретирована как преобразование из унарной системы в двоичное число.

Эффективная реализация Подсчёт единиц в битовоё строке часто требуется в криптографии и других приложениях. Расстояние Хэмминга между двумя словами A и B можно вычислить как вес Хэмминга A XOR B.

Вопрос эффективной реализации этой задачи широко изучался. Некоторые процессоры предоставляют специальные инструкции для такого вычисления или параллельные операции над битовыми векторами. Для процессоров, не обладающих такими возможностями, наилучшие известные решения основаны на суммировании счётчиков по схеме дерева. Например, чтобы подсчитать количество единичных битов в 16-битном двоичном числе a = 0110 1100 1011 1010, можно выполнить следующие операции:

Выражение Двоичные Десятичные Комментарии a 01 10 11 00 10 11 10 10 style="text-align:left;" Исходное число b0 = (a >> 0) & 01 01 01 01 01 01 01 01 01 00 01 00 00 01 00 00 1, 0, 1, 0, 0, 1, 0, 0 Каждый второй (нечётный) бит числа a b1 = (a >> 1) & 01 01 01 01 01 01 01 01 00 01 01 00 01 01 01 01 0, 1, 1, 0, 1, 1, 1, 1 оставшиеся биты числа a c = b0 + b1 01 01 10 00 01 10 01 01 1, 1, 2, 0, 1, 2, 1, 1 Число единиц в каждой паре битов числа a d0 = (c >> 0) & 0011 0011 0011 0011 0001 0000 0010 0001 1, 0, 2, 1 Каждый второй счётчик числа c d2 = (c >> 2) & 0011 0011 0011 0011 0001 0010 0001 0001 1, 2, 1, 1 Оставшиеся счётчики числа c e = d0 + d2 0010 0010 0011 0010 2, 2, 3, 2 Счётчики единиц в каждой 4-битной группе числа a f0 = (e >> 0) & 00001111 00001111 00000010 00000010 2, 2 Каждый второй счётчик числа e f4 = (e >> 4) & 00001111 00001111 00000010 00000011 2, 3 Остальные счётчики числа e g = f0 + f4 00000100 00000101 4, 5 Счётчики единиц в каждой 8-битной группе числа a h0 = (g >> 0) & 0000000011111111 0000000000000101 5 Каждый второй счётчик числа g h8 = (g >> 8) & 0000000011111111 0000000000000100 4 Остальные счётчики числа g i = h0 + h8 0000000000001001 9 Число единиц всего 16-битного слова

Здесь операции указаны в семантике языка C, так что означает сдвиг X вправо на Y бит, X & Y означает битовое AND чисел X и Y, а + является обычной операцией сложения. Лучшие известные алгоритмы для этой проблемы основываются на концепции, проиллюстрированной выше и приведены здесь:

//типы и константы, используемые в функциях ниже //uint64_t — беззнаковая 64-битная целая переменная (определена в C99 версии языка C) const uint64_t m1 = 0x5555555555555555; //двоичное: 0101... const uint64_t m2 = 0x3333333333333333; // двоичное: 00110011.. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; // двоичное: 4 нуля, 4 единицы ... const uint64_t m8 = 0x00ff00ff00ff00ff; // двоичное: 8 нуля, 8 единиц... const uint64_t m16 = 0x0000ffff0000ffff; // двоичное: 16 нуля, 16 единиц... const uint64_t m32 = 0x00000000ffffffff; // двоичное: 32 нуля, 32 единицы const uint64_t h01 = 0x0101010101010101; //сумма 256 в степени 0,1,2,3...

//Это примитивная реализация, представленная для сравнения, //чтобы помочь понять более совершенные функции //Этот алгоритм использует 24 арифметических операции (сдвиг, прибавить, и). int popcount64a(uint64_t x) { x = (x & m1 ) + ((x >> 1) & m1 ); // поместить счётчик каждых 2 бит в эти 2 бита x = (x & m2 ) + ((x >> 2) & m2 ); // поместить счётчик каждых 4 бит в эти 4 бита x = (x & m4 ) + ((x >> 4) & m4 ); // поместить счётчик каждых 8 бит в эти 8 бит x = (x & m8 ) + ((x >> 8) & m8 ); // поместить счётчик каждых 16 бит в эти 16 бит x = (x & m16) + ((x >> 16) & m16); // поместить счётчик каждых 32 бит в эти 32 бит x = (x & m32) + ((x >> 32) & m32); // поместить счётчик каждых 64 бит в эти 64 бита return x; }

// Эта реализация использует меньше арифметических операций, чем известные // другие реализации на машинах с медленным умножением. // Этот алгоритм использует 17 арифметических операций. int popcount64b(uint64_t x) { x -= (x >> 1) & m1; // поместить счётчик каждых 2 бит в эти 2 бита x = (x & m2) + ((x >> 2) & m2); // поместить счётчик каждых 4 бит в эти 4 бита x = (x + (x >> 4)) & m4; // поместить счётчик каждых 8 бит в эти 8 бит x += x >> 8; // поместить счётчик каждых 16 бит в его младшие 8 бит. x += x >> 16; // поместить счётчик каждых 32 бит в его младшие 8 бит x += x >> 32; // поместить счётчик каждых 64 бит в его младшие 8 бит return x & 0x7f; }

// Эта реализация использует меньше арифметических операций, чем известные // другие реализации на машинах с быстрым умножением. // Этот алгоритм использует 12 арифметических операций, одна из которых — умножение. int popcount64c(uint64_t x) { x -= (x >> 1) & m1; // поместить счётчик каждых 2 бит в эти 2 бита x = (x & m2) + ((x >> 2) & m2); // поместить счётчик каждых 4 бит в эти 4 бита x = (x + (x >> 4)) & m4; // поместить счётчик каждых 8 бит в эти 8 бит return (x * h01) >> 56; //вернуть левые 8 бит значения x + (x<<8) + (x<<16) + (x<<24) + ... }

Вышеприведённые реализации демонстрируют наилучшее поведение в худшем случае среди всех известных алгоритмов. Как писал Вегнер в 1960 году, побитовое AND x с x − 1 отличается от x только обнулением наименее значимого разряда. Вычитание 1 преобразует самую правовую последовательность нулей в единицы, а самую правую единицу — в нуль. Если x изначально имел n единичных бит, то после всего n итераций этой операции x превратится в нуль. Следующая реализация основана на этом принципе.

// Эта реализация лучше, когда большинство бит равны нулю // Алгоритм работает одинаково для всех размеров данных. //Этот алгоритм использует 3 арифметических операции и одно сравнение/переход на "1" бит в x. int popcount64d(uint64_t x) { int count; for (count=0; x; count++) x &= x - 1; return count; }

Здесь представляет интерес тесная связь между подсчётом числа единиц (FFS ) и число старших нулевых битов подряд (CLZ).

Если разрешено использование большее количество памяти, мы можем вычислить вес Хэмминга быстрее, чем описано выше. При неограниченной памяти мы можем просто создать большую таблицу весов Хэмминга для каждого 64-битного целого. Если мы можем запомнить таблицу функции Хэмминга каждого 16-битного целого, мы можем сделать следующее для вычисления веса Хэмминга любого 32-битного целого: static uint8_t wordbits[65536] = { /* число единиц в целых от 0 до 65535 включительно */ }; // Этот алгоритм использует 3 арифметические операции и 2 чтения из памяти. int popcount32e(uint32_t x) { return wordbits[x & 0xFFFF] + wordbits[x >> 16]; }

// Таблицу wordbits[] можно заполнить, использовав следующую функцию int popcount32e_init(void) { uint32_t i; uint16_t x; int count; for (i=0; i <= 0xFFFF; i++)

x = i; for (count=0; x; count++) // заимствовано из popcount64d() выше x &= x - 1; wordbits[i] = count;

Рекурсивный алгоритм дан в книге Донована и Кернигана /* Вес i может отличаться от веса i / 2 только в младшем разряде i */ int popcount32e_init (void) { int i; for (i = 1; sizeof wordbits / sizeof *wordbits > i; ++i) wordbits [i] = wordbits [i >> 1] + (1 & i); }

Мула и др. показали, что векторизованная версия popcount64b может работать быстрее, чем специализированные инструкции (например, popcnt на процессорах x64).

Алгоритм Харли-Сила является одним из самых быстрых среди алгоритмов, использующих только операции над целыми числами.

Минимальный вес В корректирующем коде минимальный вес Хэмминга, обычно называемый минимальным весом wmin кода — это наименьший вес кода ненулевого слова. Вес w слова — это число единиц в слове. Например, слово 11001010 имеет вес 4.

В линейном блочном коде минимальный вес является также минимальным расстоянием Хэмминга (dmin) и определяет способность коррекции ошибки кода. Если , и код будет корректным до ошибок.

Языковая поддержка Некоторые компиляторы языка C предлагают встроенные функции для подсчёта битов. Например, GCC (с версии 3.4 апреля 2004 года) содержит встроенную функцию __builtin_popcount, которая при наличии соответствующей инструкции процессора использует её, а в противном случае — эффективную библиотечную реализацию. Компилятор LLVM-GCC поддерживает эту функцию с версии 1.5 июня 2005 года.

В стандартной библиотеке C++ структура данных bitset имеет метод count(), который считает число установленных бит. В C++20 был добавлен новый заголовочный файл <bit>, содержащий функции std::popcount и std::has_single_bit, принимающие аргументы беззнаковых целочисленных типов.

В Java структура данных , расширяемый битовый массив, имеет метод , подсчитывающий количество установленных битов. Кроме того, существуют функции и для подсчёта числа бит в 32-битных и 64-битных целых соответственно. Также класс , работающий с целыми числами произвольной точности, имеет метод , который подсчитывает биты.

В Python тип int имеет метод bit_count(), который подсчитывает количество установленных битов. Эта функция появилась в Python 3.10, выпущенном в октябре 2021 года.

В Common Lisp функция logcount для неотрицательного целого числа возвращает количество единичных битов. (Для отрицательных чисел она возвращает количество нулевых битов в представлении дополнительного кода.) В обоих случаях целое число может быть BIGNUM.

Начиная с версии GHC 7.4 базовый пакет Haskell содержит функцию popCount, доступную для всех типов, реализующих класс Bits (из модуля Data.Bits).

Версия языка SQL в базе данных MySQL обеспечивает встроенную стандартную функцию BIT_COUNT().

Фортран 2008 имеют стандартную встроенную функцию popcnt, возвращающую количество ненулевых битов в целом числе (или массиве целых чисел).

Некоторые программируемые научные карманные калькуляторы имеют специальные команды для подсчёта установленных битов, например, #B на .

Free Pascal реализует popcnt начиная с версии 3.0.

Поддержка на процессорах Компьютер IBM 7030 Stretch в 1960-х годах вычислял число установленных битов, как и как побочный продукт всех логических операций.