Из Википедии, свободной энциклопедии
  (Перенаправлено из ONES )
Перейти к навигации Перейти к поиску

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

Примеры
НитьВес Хэмминга
111 0 14
111 0 1 0004
000000000
678 0 1234 0 56710
График подсчета населения (вес Хэмминга для двоичных чисел) для (десятичных) чисел от 0 до 256. [4] [5] [6]

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

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

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

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

Эффективная реализация [ править ]

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

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

ВыражениеДвоичныйДесятичная дробьКомментарий
a011011001011101027834Исходный номер
b0 = (a >> 0) & 01 01 01 01 01 01 01 0101000100000100001, 0, 1, 0, 0, 1, 0, 0Каждый другой бит от
b1 = (a >> 1) & 01 01 01 01 01 01 01 0100010100010101010, 1, 1, 0, 1, 1, 1, 1Остальные биты из
c = b0 + b101011000011001011, 1, 2, 0, 1, 2, 1, 1Подсчет единиц в каждом 2-битном срезе
d0 = (c >> 0) & 0011 0011 0011 001100010000001000011, 0, 2, 1Все остальные считают от c
d2 = (c >> 2) & 0011 0011 0011 001100010010000100011, 2, 1, 1Остальные отсчеты от c
e = d0 + d200100010001100102, 2, 3, 2Подсчет единиц в каждом 4-битном срезе
f0 = (e >> 0) & 00001111 0000111100000010000000102, 2Все остальные считают от е
f4 = (e >> 4) & 00001111 0000111100000010000000112, 3Остальные отсчеты от e
g = f0 + f400000100000001014, 5Подсчет единиц в каждом 8-битном срезе
h0 = (g >> 0) & 000000001111111100000000000001015Все остальные считают от g
h8 = (g >> 8) & 000000001111111100000000000001004Остальные отсчеты от g
i = h0 + h800000000000010019Подсчет единиц во всем 16-битном слове

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

// типы и константы, используемые в приведенных ниже функциях // 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  =  (х  +  ( х  >>  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 =  ( х  +  ( х  >>  4 ))  &  m4 ;  // помещаем количество каждых 8 битов в эти 8 бит  return  ( x  *  h01 )  >>  56 ;  // возвращает 8 левых битов x + (x << 8) + (x << 16) + (x << 24) + ... }

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

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

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

static  uint8_t  wordbits [ 65536 ]  =  {  / * количество битов целых чисел от 0 до 65535 включительно * /  }; // Этот алгоритм использует 3 арифметических операции и 2 чтения из памяти. int  popcount32e ( uint32_t  x ) {  вернуть  биты слова [ x  &  0xFFFF ]  +  биты слова [ x  >>  16 ]; }
// Необязательно, таблица wordbits [] может быть заполнена с помощью этой функции int  popcount32e_init ( void ) {  uint32_t  i ;  uint16_t  x ;  int  count ;  для  ( я = 0 ;  я  <=  0xFFFF ;  я ++ )  {  х  =  я ;  for  ( count = 0 ;  x ;  count ++ )  // заимствовано из popcount64d () выше  x  & =  x -  1 ;  wordbits [ я ]  =  счетчик ;  } }

Muła et al. [14] показали, что векторизованная версия popcount64b может работать быстрее, чем выделенные инструкции (например, popcnt на процессорах x64).

Минимальный вес [ править ]

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

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

Языковая поддержка [ править ]

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

В 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 год [18].

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

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

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

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

Некоторые программируемые карманные научные калькуляторы имеют специальные команды для вычисления количества установленных битов, например, #Bна HP-16C [3] [22] и WP 43S , [23] [24] #BITS[25] [26] или BITSUM[27] [28 ] ] на эмуляторах HP-16C и nBITSна WP 34S . [29] [30]

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

Поддержка процессора [ править ]

  • IBM STRETCH компьютер в 1960 - х годах подсчитан число установленных бит, а также ряд ведущих нулей в качестве побочного продукта всех логических операций. [1]
  • Вначале суперкомпьютеры Cray имели машинную команду подсчета населения, которая , по слухам, была специально запрошена Агентством национальной безопасности США для приложений криптоанализа . [1]
  • Некоторые из машин серии Cyber ​​70/170 компании Control Data Corporation (CDC) включали в себя инструкцию по подсчету населения; в КОМПАСЕ эта инструкция была закодирована как .CXi
  • 64-битная архитектура SPARC версии 9 определяет POPCинструкцию [11] [1], но большинство реализаций ее не реализуют, требуя ее эмуляции операционной системой. [32]
  • Модель MMIX Дональда Кнута, которая заменит MIX в его книге «Искусство компьютерного программирования», имеет SADDинструкцию с 1999 года. SADD a,b,cСчитает все биты, которые равны 1 в b и 0 в c, и записывает результат в a.
  • Compaq «ы Альфа 21264A , выпущенный в 1999 году, был первым альфа дизайн серии процессоров , которые имели расширение счетчика ( CIX).
  • Analog Devices ' Blackfin процессоры имеют в ONESинструкции для выполнения 32-битного счетчика населения. [33]
  • Архитектура 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). [34]

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Б с д е е г Уоррен младший, Генри S. (2013) [2002]. Восторг хакера (2-е изд.). Эддисон Уэсли - Pearson Education, Inc., стр. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
  2. ^ Кнут, Дональд Эрвин (2009). «Побитовые приемы и методы; двоичные диаграммы решений». Искусство программирования . Том 4, выпуск 1. Эддисон – Уэсли Профессионал . ISBN 978-0-321-58050-4.(NB. Черновик Послания 1b доступен для загрузки.)
  3. ^ a b Руководство пользователя компьютерного ученого Hewlett-Packard HP-16C (PDF) . Компания Hewlett-Packard . Апрель 1982 г. 00016-90001. Архивировано (PDF) из оригинала 28 марта 2017 года . Проверено 28 марта 2017 .
  4. ^ [1] , написано на языке Fōrmulæ. Вики по Fōrmulæ . Проверено 30 сентября 2019.
  5. ^ Решение задачи Подсчет населения . Проверено 30 сентября 2019.
  6. ^ Rosetta Code . Проверено 30 сентября 2019.
  7. ^ Томпсон, Томас М. (1983). От кодов с исправлением ошибок до сферических упаковок и простых групп . Математические монографии Каруса № 21. Математическая ассоциация Америки . п. 33.
  8. ^ Glaisher, Джеймс Уайтбрид Ли (1899). «О вычете коэффициента теоремы бинома относительно простого модуля» . Ежеквартальный журнал чистой и прикладной математики . 30 : 150–156. (NB. См., В частности, последний абзац на стр. 156.)
  9. ^ Рид, Ирвинг Стой (1954). «Класс кодов с множественным исправлением ошибок и схема декодирования». Профессиональная группа IRE по теории информации . Институт Радиоинженеров (ИРЭ). ПГИТ-4: 38–49.
  10. ^ Stoica, I .; Morris, R .; Liben-Nowell, D .; Karger, DR; Kaashoek, MF; Дабек, Ф .; Балакришнан, Х. (февраль 2003 г.). «Chord: масштабируемый протокол однорангового поиска для интернет-приложений». Транзакции IEEE / ACM в сети . 11 (1): 17–32. DOI : 10.1109 / TNET.2002.808407 . S2CID 221276912 . Раздел 6.3: «В общем, количество пальцев, которым мы должны следовать, будет количеством единиц в двоичном представлении расстояния от узла до запроса». 
  11. ^ а б SPARC International, Inc. (1992). «A.41: Счетчик населения. Примечание по программированию» . Руководство по архитектуре SPARC: версия 8 (версия 8 - ред.). Энглвуд Клиффс, Нью-Джерси, США: Прентис Холл . С.  231 . ISBN 0-13-825001-4.
  12. ^ Blaxell, Дэвид (1978). Хогбен, Дэвид; Файф, Деннис В. (ред.). «Связывание записи по битовому шаблону» . Компьютерные науки и статистика - десятый ежегодный симпозиум по интерфейсу . Специальное издание NBS. Министерство торговли США / Национальное бюро стандартов . 503 : 146–156.
  13. ^ Вегнер, Питер (май 1960). «Методика счета единиц в двоичном компьютере». Коммуникации ACM . 3 (5): 322. DOI : 10,1145 / 367236,367286 . S2CID 31683715 . 
  14. ^ Мула, Войцех; Курц, Натан; Лемир, Даниэль (январь 2018 г.). «Более быстрый подсчет населения с помощью инструкций AVX2». Компьютерный журнал . 61 (1): 111–120. arXiv : 1611.07612 . DOI : 10.1093 / comjnl / bxx046 . S2CID 540973 . 
  15. ^ Стерн и Махмуд, Дизайн систем связи , Прентис Холл , 2004, стр. 477 и далее.
  16. ^ «Примечания к выпуску GCC 3.4» . Проект GNU .
  17. ^ «Примечания к выпуску LLVM 1.5» . LLVM Project .
  18. ^ «Что нового в Python 3.10» . python.org .
  19. ^ «Примечания к выпуску GHC 7.4.1» . Документация GHC.
  20. ^ «Глава 12.11. Битовые функции - Справочное руководство MySQL 5.0» .
  21. ^ Меткалф, Майкл; Рид, Джон; Коэн, Малкольм (2011). Объяснение современного Фортрана . Издательство Оксфордского университета . п. 380. ISBN 978-0-19-960142-4.
  22. ^ Шварц, Джейк; Гревелл, Рик (2003-10-20) [1993]. Библиотека эмулятора HP16C для HP48S / SX . 1.20 (1-е изд.) . Проверено 15 августа 2015 .(NB. Эта библиотека также работает на HP 48G / GX / G + . Помимо набора функций HP-16C, этот пакет также поддерживает вычисления для двоичных, восьмеричных и шестнадцатеричных чисел с плавающей запятой в экспоненциальном представлении в дополнение к обычным десятичным числа с плавающей запятой.)
  23. ^ Бонин, Уолтер (2019) [2015]. Руководство пользователя WP 43S (PDF) . 0,12 (черновик ред.). п. 135. ISBN  978-1-72950098-9. Проверено 5 августа 2019 . [2] [3] (314 стр.)
  24. ^ Бонин, Уолтер (2019) [2015]. Справочное руководство WP 43S (PDF) . 0,12 (черновик ред.). стр. xiii, 104, 115, 120, 188. ISBN  978-1-72950106-1. Проверено 5 августа 2019 . [4] [5] (271 стр.)
  25. ^ Мартин, Анхель М .; МакКлюр, Грег Дж. (05.09.2015). «Модуль эмулятора HP16C для HP-41CX - Руководство пользователя и QRG» (PDF) . Архивировано (PDF) из оригинала 27 апреля 2017 года . Проверено 27 апреля 2017 . (NB. Помимо набора функций HP-16C, эта настраиваемая библиотека для HP-41CX расширяет функциональные возможности калькулятора примерно на 50 дополнительных функций.)
  26. ^ Мартин, Анхель М. (2015-09-07). «HP-41: Доступен новый эмулятор HP-16C» . Архивировано 27 апреля 2017 года . Проверено 27 апреля 2017 .
  27. ^ Thörngren, Хакан (2017-01-10). "Божья коровка Документация" (выпуск 0A ред.) . Проверено 29 января 2017 . [6]
  28. ^ "Доступен новый модуль HP-41: Божья коровка" . 2017-01-10. Архивировано 29 января 2017 года . Проверено 29 января 2017 .
  29. ^ Дейл, Пол; Бонин, Вальтер (2012) [2008]. «Руководство пользователя WP 34S» (PDF) (изд. 3.1) . Проверено 27 апреля 2017 .
  30. ^ Бонин, Уолтер (2015) [2008]. Руководство пользователя WP 34S (3.3-е изд.). ISBN 978-1-5078-9107-0.
  31. ^ "Free Pascal documentation popcnt" . Проверено 7 декабря 2019 .
  32. ^ "JDK-6378821: bitCount () должен использовать POPC на процессорах SPARC и AMD + 10h" . База данных ошибок Java . 2006-01-30.
  33. ^ Справочник по набору команд Blackfin (предварительная редакция). Аналоговые устройства . 2001. С. 8–24. Каталожный номер 82-000410-14.
  34. ^ Вольф, Клиффорд (22.03.2019). "RISC-V" B "Расширение управления битами для RISC-V, проект v0.37" (PDF) . Github .

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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