Вес Хэмминга

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

Примеры

Нить	Вес Хэмминга
111 0 1	4
111 0 1 000	4
00000000	0
678 0 1234 0 567	10

График веса Хэмминга для чисел от 0 до 256.

История и использование

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

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

• При модульном возведении в степень возведением в квадрат количество модульных умножений, необходимых для показателя e, равно log ₂ e + Weight( e ). По этой причине значение открытого ключа e, используемое в RSA, обычно выбирается как число с низким весом Хэмминга.
• Вес Хэмминга определяет длину путей между узлами в распределенных хеш-таблицах Chord .
• Поиск IrisCode в биометрических базах данных обычно реализуется путем расчета расстояния Хэмминга до каждой сохраненной записи.
• В компьютерных шахматных программах, использующих представление битовой доски , вес Хэмминга битовой доски дает количество фигур данного типа, оставшихся в игре, или количество клеток доски, контролируемых фигурами одного игрока, и, следовательно, является важным способствующим фактором. к стоимости позиции.
• Вес Хэмминга можно использовать для эффективного вычисления первого набора поиска, используя тождество ffs(x) = pop(x ^ (x - 1)). Это полезно на таких платформах, как SPARC , где есть аппаратные инструкции по весу Хэмминга, но нет аппаратных инструкций по поиску первого набора.
• Весовую операцию Хэмминга можно интерпретировать как преобразование унарной системы счисления в двоичную систему чисел .
• В реализации некоторых кратких структур данных, таких как битовые векторы и деревья вейвлетов .

Эффективная реализация

Подсчет численности битовой строки часто необходим в криптографии и других приложениях. Расстояние Хэмминга двух слов A и B можно рассчитать как вес Хэмминга A xor B .

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

Выражение	Двоичный								Десятичный	Комментарий
a	01	10	11	00	10	11	10	10	27834	Исходный номер
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	Каждый второй бит из
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	Остальные биты из
c = b0 + b1	01	01	10	00	01	10	01	01	1, 1, 2, 0, 1, 2, 1, 1	Количество единиц в каждом 2-битном фрагменте
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-битном фрагменте
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-битном фрагменте
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 бит, X & Y означает побитовое И X и Y, а + — обычное сложение. Лучшие алгоритмы, известные для решения этой проблемы, основаны на концепции, проиллюстрированной выше, и приведены здесь:

//types and constants used in the functions below
//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (shift, add, and).
int popcount64a(uint64_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits 
    return x;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//This algorithm uses 17 arithmetic operations.
int popcount64b(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x & 0x7f;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//This algorithm uses 12 arithmetic operations, one of which is a multiply.
int popcount64c(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

Вышеупомянутые реализации имеют лучшее поведение в наихудшем случае из всех известных алгоритмов. Однако, когда ожидается, что значение будет иметь несколько ненулевых битов, вместо этого может быть более эффективно использовать алгоритмы, которые считают эти биты по одному. Как описал Вегнер в 1960 году, побитовое И для x с x - 1 отличается от x только обнулением младшего значащего ненулевого бита: вычитание 1 изменяет самую правую строку из 0 на 1 и меняет крайнюю правую 1 на 0. Если x изначально имел n бит, которые были 1, то всего лишь после n итераций этой операции x уменьшится до нуля. Следующая реализация основана на этом принципе.

//This is better when most bits in x are 0
//This algorithm works the same for all data sizes.
//This algorithm uses 3 arithmetic operations and 1 comparison/branch per "1" bit in x.
int popcount64d(uint64_t x)
{
    int count;
    for (count=0; x; count++)
        x &= x - 1;
    return count;
}

Если разрешено большее использование памяти, мы можем вычислить вес Хэмминга быстрее, чем описанные выше методы. Имея неограниченную память, мы могли бы просто создать большую таблицу поиска веса Хэмминга для каждого 64-битного целого числа. Если мы можем сохранить таблицу поиска функции Хэмминга для каждого 16-битного целого числа, мы можем сделать следующее, чтобы вычислить вес Хэмминга каждого 32-битного целого числа.

static uint8_t wordbits[65536] = { /* bitcounts of integers 0 through 65535, inclusive */ };
//This algorithm uses 3 arithmetic operations and 2 memory reads.
int popcount32e(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//Optionally, the wordbits[] table could be filled using this function
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++) // borrowed from popcount64d() above
            x &= x - 1;
        wordbits[i] = count;
    }
}

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

Минимальный вес

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

В линейном блочном коде минимальный вес также является минимальным расстоянием Хэмминга ( d _min ) и определяет способность кода исправлять ошибки. Если w _min = n , то d _min = n и код исправит до d _min /2 ошибок.

Языковая поддержка

Некоторые компиляторы 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 — расширяемая структура данных битового массива. BitSet имеет BitSet.cardinality() метод, который подсчитывает количество установленных битов. Кроме того, существуют Integer.bitCount(int) и Long.bitCount(long) функции для подсчета битов в примитивных 32-битных и 64-битных целых числах соответственно. Кроме того, BigInteger Целочисленный класс произвольной точности также имеет BigInteger.bitCount() метод, который считает биты.

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

В Common Lisp функция logcount, учитывая неотрицательное целое число, возвращает количество 1 бит. (Для отрицательных целых чисел возвращается количество нулевых битов в записи дополнения до 2.) В любом случае целое число может быть БОЛЬШИМ ЧИСЛОМ.

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

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

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

Некоторые программируемые карманные научные калькуляторы имеют специальные команды для расчета количества установленных бит, например #B на НР-16С и WP 43S , #BITS или BITSUM на эмуляторах HP-16C и nBITS на WP 34S .

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

Поддержка процессора

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

См. также

• Дополнение до двух
• Веер

Дальнейшее чтение

• Шреппель, Ричард К .; Орман, Хилари К. (29 февраля 1972 г.). «сборник». ХАКМЕМ . Билер, Майкл; Госпер, Ральф Уильям ; Шреппель, Ричард К. (отчет). искусственного интеллекта Лаборатория Массачусетского технологического института , Кембридж, Массачусетс, США. Памятка MIT AI 239. ( Поз. 169 : Код сборки подсчета населения для PDP/6-10.)

Внешние ссылки

• Агрегатные магические алгоритмы . Оптимизированный подсчет населения и другие алгоритмы, объясненные с помощью примера кода.
• Bit Twiddling Hacks Несколько алгоритмов с набором кода для подсчета битов.
• Необходимое и достаточное. Архивировано 23 сентября 2017 г. в Wayback Machine. Автор: Дэмиен Винтур. Содержит код на C# для различных реализаций веса Хэмминга.
• Лучший алгоритм для подсчета количества установленных бит в 32-битном целом числе? - Переполнение стека