Вес Хэмминга

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

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

Вес Хэмминга используется в некоторых дисциплинах, включая теорию информации, теорию кодирования и криптографию. Примеры приложений веса Хэмминга включают:

• В алгоритме модульного быстрого возведения в степень, число модульных умножений, требуемых для степени n, равно log₂ n + вес(n). Именно поэтому в качестве публичного ключа n, используемого в RSA, обычно выбирается число с низким весом Хэмминга^[7].
• Вес Хэмминга определяет длины путей между узлами в распределённых хеш-таблицах Chord^[8].
• Поиск радужной оболочки глаза в биометрических базах данных обычно реализуется путём вычисления расстояния Хэмминга для каждой записи^[9].
• В программах компьютерных шахмат, использующих представление битовой карты, вес Хэмминга битовой карты указывает количество оставшихся фигур определённого типа или количество клеток доски, контролируемых фигурами одного игрока, и поэтому является важным фактором, влияющим на оценку позиции^[10].
• Вес Хэмминга может быть использован для эффективного нахождения первого установленного бита используя равенство ffs(x) = pop(x ^ (x - 1)). Это полезно на платформах, таких как SPARC, которые имеют аппаратные инструкции для подсчёта веса Хэмминга, но не имеют аппаратной инструкции для поиска первого установленного бита^[11][12].
• Операция вычисления веса Хэмминга может быть интерпретирована как преобразование из унарной системы в двоичное число^[13].

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

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

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

//типы и константы, используемые в функциях ниже
//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 году^[14], побитовое 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;
    }
}

Рекурсивный алгоритм дан в книге Донована и Кернигана^[15]

/* Вес 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);
}

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

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

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

В линейном блочном коде минимальный вес является также минимальным расстоянием Хэмминга (d_min) и определяет способность коррекции ошибки кода. Если ${\displaystyle w_{min}=n}$, ${\displaystyle d_{min}=n}$ и код будет корректным до ${\displaystyle d_{min}/2}$ ошибок^[19].

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

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

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

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

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

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

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

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

Некоторые программируемые научные карманные калькуляторы имеют специальные команды для подсчёта установленных битов, например, #B на HP-16C^[26].

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

• Компьютер IBM 7030 Stretch в 1960-х годах вычислял число установленных битов, как и число ведущих нулей как побочный продукт всех логических операций^[12].
• Ранние суперкомпьютеры Cray имели инструкцию подсчёта количества установленных битов, которая, по слухам, была специально запрошена Агентство национальной безопасности США для приложений криптоанализа^[12].
• В машинах серий 6000 и Cyber 70/170 компании Control Data Corporation также присутствовала инструкция подсчёта битов. В ассемблере COMPASS она кодировалась как CXi.
• 64-битная архитектура SPARC версии 9 определяет инструкцию POPC^[11][12], однако большинство реализаций её не поддерживают, и она эмулируется операционной системой^[28].
• Модель компьютера MMIX, разработанная Дональдом Кнутом для замены MIX в его книге Искусство программирования с 1999 года имеет инструкцию SADD. Инструкция SADD a,b,c подсчитывает все единичные биты в b, которые одновременно являются нулевыми в c и записывает результат в a.
• Процессор Compaq Alpha 21264, выпущенный в 1999 году, стал первым в серии Alpha, в котором была реализована инструкция подсчёта (CIX).
• Процессоры Blackfin от Analog Devices оснащены инструкцией ONES для выполнения 32-битного подсчёта установленных битов^[29].
• Архитектура Barcelona от AMD представила набор инструкций для продвинутой битовой манипуляции, включающий инструкцию POPCNT в составе расширений SSE4a в 2007 году.
• Процессоры Intel Core получили инструкцию POPCNT в составе расширения SSE4.2 системы команд, впервые появившегося в процессоре Core i7 на базе Nehalem, выпущенном в ноябре 2008 года.
• Архитектура ARM представила инструкцию VCNT как часть расширений Advanced SIMD (NEON).
• Архитектура RISC-V добавила инструкцию CPOP как часть расширения Bit Manipulation (B)^[30].

• Дополнительный код
• Нагрузочная способность выхода цифровой микросхемы

• Michael Beeler, Ralph William Gosper, Richard C. Schroeppel. compilation // HAKMEM. — Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA, 1972. (Item 169: Population count assembly code for the PDP/6-10.)

В английском языке вес Хэмминга в бинарном случае называется также population count^[1], popcount, sideways sum^[2] или bit summation^[3].

• Aggregate Magic Algorithms. Optimized population count and other algorithms explained with sample code.
• Bit Twiddling Hacks Several algorithms with code for counting bits set.
• Necessary and Sufficient Архивировано 23 сентября 2017 года. - by Damien Wintour - Has code in C# for various Вес Хэмминга implementations.
• Best algorithm to count the number of set bits in a 32-bit integer? - Stackoverflow

1. ↑ Warren Jr., 2013, с. 81–96.
2. ↑ Knuth, 2009.
3. ↑ HP-16C, 1982.