Вес Хэмминга - Hamming weight

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

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

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

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

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

Эффективное внедрение

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

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

Здесь операции такие же, как в языке программирования 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;
    }
}

Muła et al. показали, что векторизованная версия 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 ++ STL структура данных битового массива 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, учитывая неотрицательное целое число, возвращает количество битов, равное единице. (Для отрицательных целых чисел он возвращает количество 0 бит в нотации дополнения до 2.) В любом случае целое число может быть BIGNUM.

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

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

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

Некоторые программируемые карманные калькуляторы для научных исследований имеют специальные команды для вычисления количества установленных битов, например, #Bна HP-16C и 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 включали в себя инструкцию по подсчету населения; в КОМПАСЕ эта инструкция была закодирована как CXi.
• 64-битная архитектура SPARC версии 9 определяет POPCинструкцию, но большинство реализаций ее не реализуют, требуя ее эмуляции операционной системой.
• Модель MMIX Дональда Кнута, которая заменит MIX в его книге «Искусство компьютерного программирования», имеет SADDинструкцию с 1999 года. SADD a,b,cСчитает все биты, которые равны 1 в b и 0 в c, и записывает результат в a.
• Compaq «ы Альфа 21264A , выпущенный в 1999 году, был первым альфа дизайн серии процессоров , которые имели расширение счетчика ( CIX).
• Analog Devices ' Blackfin процессоры имеют в ONESинструкции для выполнения 32-битного счетчика населения.
• Архитектура AMD « Барселона» представила ISA расширенного управления битами (ABM), представив POPCNTинструкцию как часть расширений SSE4a в 2007 году.
• Intel Core процессоры представили POPCNTинструкцию с SSE4.2 набором команд расширения, первым доступным в Nehalem - Core i7 процессора, выпущенном в ноябре 2008 года.
• Архитектура ARM представила VCNTинструкцию как часть расширений Advanced SIMD ( NEON ).
• Архитектура RISC-V представила PCNTинструкцию как часть расширения Bit Manipulation (B).

Смотрите также

• Два дополнения
• Наиболее часто встречающиеся символы k
• Развернуть веер

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

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

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

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

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