Как найти вес кода заданного битовой строкой

Рассмотрим,
чем определяется способность блочного
кода обнаруживать и исправлять ошибки,
возникшие при передаче.

Пусть
U
= (U₀,
U₁,
U₂,
…U_n-1)
– двоичная последовательность длиной
n.

Число
единиц
(ненулевых компонент) в этой
последовательности называется
весом
Хемминга
вектора U
и обозначается w(U).

Например,
вес Хемминга вектора U
=
( 1001011
) равен четырем, для вектора U
=
( 1111111
)
величина w(U)
составит 7 и т.д.

Таким
образом, чем больше единиц в двоичной
последовательности, тем больше ее вес
Хемминга.

Далее, пусть U и V будут
двоичными последовательностями длиной
n.

Число разрядов, в которых эти
последовательности различаются,
называется расстоянием Хемминга между
U и V и обозначается
d( U, V).

Например,
если U
=
( 1001011
), а V
= ( 0100011
), то d(
U, V) = 3.

Задав
линейный код, то есть определив все 2^k
его кодовых слов, можно вычислить
расстояние между всеми возможными
парами кодовых слов. Минимальное из них
называется минимальным
кодовым расстоянием кода
и обозначается d_min.

Можно
проверить и убедиться, что минимальное
кодовое расстояние для рассматриваемого
нами в примерах (7,4)-кода
равно трем: d_min(7,4)
=
3.
Для этого нужно записать все кодовые
слова (7,4)-кода
Хемминга (всего 16 слов), вычислить
расстояния между их всеми парами и взять
наименьшее значение. Однако можно
определить d_min
блочного кода и более простым способом.

Доказано,
что расстояние между нулевым кодовым
словом и одним из кодовых слов, входящих
в порождающую матрицу (строки порождающей
матрицы линейного блочного кода сами
являются кодовыми словами, по определению),
равно d_min.
Но расстояние от любого кодового слова
до нулевого равно весу Хемминга этого
слова. Тогда d_min
равно минимальному
весу Хемминга
для
всех строк порождающей матрицы кода .

Если
при передаче кодового слова по каналу
связи в нем произошла одиночная
ошибка,
то расстояние Хемминга между переданным
словом U
и принятым вектором r

будет равно единице. Если при этом одно
кодовое слово не перешло в другое (а при
d_min
>
1 и при одиночной ошибке это невозможно),
то ошибка будет
обнаружена
при декодировании.

В
общем случае если блочный код имеет
минимальное расстояние d_min,
то он
может обнаруживать любые сочетания
ошибок при их числе, меньшем или равном
d_min
–
1,
поскольку никакое сочетание ошибок при
их числе, меньшем, чем d_min
–
1,
не может перевести одно кодовое слово
в другое.

Но
ошибки могут иметь кратность и большую,
чем d_min–
1,
и тогда они останутся
необнаруженными.

При
этом среднюю вероятность необнаруживаемой
ошибки можно определить следующим
образом.

Пусть
вероятность ошибки в канале связи равна
P_ош.
Тогда вероятность того, что при передаче
последовательности длины n
в ней произойдет одна ошибка, равна

Р₁
= n
P_ош

( 1- Р_ош)^n-1,
(1.36)

соответственно,
вероятность l-кратной
ошибки –

P_l
=C_n^l
P_ош^l

( 1- P_ош)^n-l,
(1.37)

где
C_n^l
– число возможных комбинаций из
n
символов кодовой последо-вательности
по l
ошибок.

По
каналу связи передаются кодовые слова
с различными весами Хемминга. Положим,
что a_i

— число слов с весом i
в данном коде (всего слов в коде длиной
n
–

).

А
теперь определим, что такое необнаруживаемая
ошибка.
Обнаружение ошибки производится путем
вычисления синдрома принятой
последовательности. Если принятая
последовательность не является кодовым
словом ( тогда синдром не равен нулю),
то считается, что ошибка есть. Если же
синдром равен нулю, то полагаем, что
ошибки нет (принятая последовательность
является кодовым словом). Но
тем ли, которое передавалось? Или же в
результате действия ошибок переданное
кодовое слово перешло в другое кодовое
слово данного кода:

r
= U
+ е = V,
(1.38)

то
есть сумма переданного кодового слова
U
и вектора ошибки е
даст новое
кодовое слово V
? В этом случае, естественно, ошибка
обнаружена быть не может.

Но
из определения двоичного линейного
кода следует, что если
сумма кодового слова и некоторого
вектора е
есть кодовое слово, то вектор е
также представляет собой кодовое слово.
Следовательно,
необнаруживаемые ошибки будут возникать
тогда, когда сочетания ошибок будут
образовывать кодовые слова.

Вероятность
того, что вектор е
совпадает с кодовым словом, имеющим вес
i
,
равна

P_i
=
P_ошⁱ

(1- Р_ош)^n-i
. (1.39)

Тогда полная
вероятность возникновения необнаруживаемой
ошибки

.
(1.40)

Пример:
рассматриваемый нами (7,4)-код
содержит по семь кодовых слов с весами
w
= 3 и w
= 4 и одно
кодовое слово с весом w
= 7, тогда

(1.41)

или,
при Р_ош
= 10
^-3,
Р(Е) 
7 
10
^-9.

Другими
словами, если по каналу передается
информация
со скоростью V
=
1кбит/с и в канале в среднем каждую
секунду
будет происходить искажение одного
символа, то в среднем семь принятых слов
на 10⁹
переданных будут проходить через декодер
без обнаружения ошибки (одна необнаруживаемая
ошибка за 270 часов).

Таким
образом, использование даже такого
простого кода позволяет на несколько
порядков снизить вероятность
необнаруживаемых ошибок.

Теперь
предположим, что линейный блочный код
используется для исправления ошибок.
Чем определяются его возможности по
исправлению?

Рассмотрим
пример, приведенный на рис. 1.9. Пусть U
и V
представляют
пару кодовых слов кода с
кодовым расстоянием d
,
равным минимальному — d
_min

для

данного
кода.

Рис.
1.9

Предположим,
передано кодовое слово U,
в
канале произошла одиночная
ошибка
и принят вектор а

(не
принадлежащий коду).

Если
декодирование производится оптимальным
способом, то есть по
методу максимального правдоподобия,
то в
качестве оценки U^*
нужно
выбрать ближайшее к а
кодовое
слово.

Таковым
в данном случае будет U,
следовательно, ошибка будет устранена.

Представим
теперь, что произошло две ошибки и принят
вектор b.

Тогда
при декодировании по максимуму
правдоподобия в
качестве оценки будет выбрано ближайшее
к b
кодовое слово, и им будет
V.
Произойдет ошибка декодирования.

Продолжив
рассуждения для d_min
=
4, d_min
=
5
и т.д., нетрудно сделать вывод, что ошибки
будут устранены, если их кратность l
не превышает величины

l<
INT (( dmin – 1 )/2) ,
(1.41)

где
INT (X)
— целая часть Х.

Так,
используемый нами в качестве примера
(7,4)-код
имеет d_min
= 3 и,
следовательно, позволяет
исправлять лишь одиночные ошибки:

l
= INT
(( d_min
– 1
)/2)=INT((3-1)/2)=1
.
(1.42)

Таким
образом, возможности
линейных блочных кодов по обнаружению
и исправлению ошибок определяются их
минимальным кодовым расстоянием.
Чем
больше d_min,
тем большее число ошибок в принятой
последовательности можно исправить.

А
теперь определим вероятность того, что
возникшая в процессе передачи ошибка
не будет все же исправлена при
декодировании.

Пусть,
как и ранее, вероятность ошибки в канале
будет равна Р_ош.
Ошибки, возникающие в различных позициях
кода, считаем независимыми.

Вероятность
того, что принятый вектор r
будет иметь какие-нибудь (одиночные,
двукратные, трехкратные и т.д.) ошибки,
можно определить как

Р_ош
= P₁
+ P₂
+ P₃
+… + P_n
,
(1.43)

где
Р₁
— вероятность того, что в r
присутствует
одиночная ошибка;

Р₂
—
вероятность того, что ошибка двойная и
т.д.;

Р_n
— вероятность того, что все n
символов
искажены.

Определим вероятность ошибок заданной
кратности:

Р₁
=
Вер{ошибка
в 1-й позиции ИЛИ ошибка во 2-й позиции
..ИЛИ в n-й позиции}
= = Р_ош(1-
Р_ош)^n-1
+ Р_ош(1-
Р_ош)^n-1
+…Р_ош(1-
Р_ош)^n-1
= п 
Р_ош(1-
Р_ош)^n-;
(1.44)

Р₂
=
Вер{ошибка
в 1-й И во 2-й позиции ИЛИ ошибка во 2-й И
в 3-й позиции…}
=

=
P²_ош(1-Р_ош)^n-2
+…Р²_ош(1-
Р_ош)
^n-2 =

Р²_ош(1-
Р_ош)
^n-2.
(1.45)

Аналогичным
образом

Р₃
=

Р³_ош(1-
Р_ош)^n-3
и т.д.
(1.46)

Декодер,
как мы показали, исправляет все ошибки,
кратность которых не превышает

,
(1.47)

то
есть все ошибки кратности J

l будут
исправлены.

Тогда
ошибки декодирования – это ошибки с
кратностью, большей кратности исправляемых
ошибок l,

и их вероятность

.
(1.48)

Для
(7,4)-кода
Хемминга минимальное расстояние d_min
=
3,
т.е. l
=
1.
Следовательно, ошибки кратности 2 и
более исправлены не будут и

.
(1.49)

Если
Р_ош<<
1,
можно считать (1-
Р_ош)

1
и, кроме того, Р³_ош<<
Р²_ош.
Тогда

.
(1.50)

Так, например,
при вероятности ошибки в канале Р_ош
= 10 ^-3 вероятность
неисправления ошибки Р(N) 
2 10
^-5, то есть при такой
вероятности ошибок в канале кодирование
(7.4)-кодом позволяет снизить
вероятность оставшихся неисправленными
ошибок примерно в пятьдесят раз.

Если
же вероятность ошибки в канале будет
в сто раз меньше Р_ош
= 10 ^-5, то вероятность
ее неисправления составит уже Р(N)

210
^-9, или в 5000 раз
меньше!

Таким
образом, выигрыш от помехоустойчивого
кодирования (который можно определить
как отношение числа ошибок в канале к
числу оставшихся неисправленными
ошибок) существенно зависит от свойств
канала связи.

Если
вероятность ошибок в канале велика, то
есть канал не очень хороший, ожидать
большого эффекта от кодирования не
приходится, если же вероятность ошибок
в канале мала, то корректирующее
кодирование уменьшает ее в значительно
большей степени.

Другими
словами, помехоустойчивое кодирование
существенно улучшает свойства хороших
каналов, в плохих же каналах оно большого
эффекта не дает.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #

  10.06.2015684.82 Кб14P4.pdf

• #
• #
• #
• #

From Wikipedia, the free encyclopedia

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1’s in the string, or the digit sum of the binary representation of a given number and the ℓ₁ norm of a bit vector. In this binary case, it is also called the population count,^[1] popcount, sideways sum,^[2] or bit summation.^[3]

History and usage[edit]

The Hamming weight is named after Richard Hamming although he did not originate the notion.^[7] The Hamming weight of binary numbers was already used in 1899 by James W. L. Glaisher to give a formula for the number of odd binomial coefficients in a single row of Pascal’s triangle.^[8] Irving S. Reed introduced a concept, equivalent to Hamming weight in the binary case, in 1954.^[9]

Hamming weight is used in several disciplines including information theory, coding theory, and cryptography. Examples of applications of the Hamming weight include:

• In modular exponentiation by squaring, the number of modular multiplications required for an exponent e is log₂ e + weight(e). This is the reason that the public key value e used in RSA is typically chosen to be a number of low Hamming weight.^[10]
• The Hamming weight determines path lengths between nodes in Chord distributed hash tables.^[11]
• IrisCode lookups in biometric databases are typically implemented by calculating the Hamming distance to each stored record.
• In computer chess programs using a bitboard representation, the Hamming weight of a bitboard gives the number of pieces of a given type remaining in the game, or the number of squares of the board controlled by one player’s pieces, and is therefore an important contributing term to the value of a position.
• Hamming weight can be used to efficiently compute find first set using the identity ffs(x) = pop(x ^ (x – 1)). This is useful on platforms such as SPARC that have hardware Hamming weight instructions but no hardware find first set instruction.^[12][1]
• The Hamming weight operation can be interpreted as a conversion from the unary numeral system to binary numbers.^[13]
• In implementation of some succinct data structures like bit vectors and wavelet trees.

Efficient implementation[edit]

The population count of a bitstring is often needed in cryptography and other applications. The Hamming distance of two words A and B can be calculated as the Hamming weight of A xor B.^[1]

The problem of how to implement it efficiently has been widely studied. A single operation for the calculation, or parallel operations on bit vectors are available on some processors. For processors lacking those features, the best solutions known are based on adding counts in a tree pattern. For example, to count the number of 1 bits in the 16-bit binary number a = 0110 1100 1011 1010, these operations can be done:

Here, the operations are as in C programming language, so X >> Y means to shift X right by Y bits, X & Y means the bitwise AND of X and Y, and + is ordinary addition. The best algorithms known for this problem are based on the concept illustrated above and are given here:^[1]

//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) + ... 
}

The above implementations have the best worst-case behavior of any known algorithm. However, when a value is expected to have few nonzero bits, it may instead be more efficient to use algorithms that count these bits one at a time. As Wegner described in 1960,^[14] the bitwise AND of x with x − 1 differs from x only in zeroing out the least significant nonzero bit: subtracting 1 changes the rightmost string of 0s to 1s, and changes the rightmost 1 to a 0. If x originally had n bits that were 1, then after only n iterations of this operation, x will be reduced to zero. The following implementation is based on this principle.

//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;
}

If greater memory usage is allowed, we can calculate the Hamming weight faster than the above methods. With unlimited memory, we could simply create a large lookup table of the Hamming weight of every 64 bit integer. If we can store a lookup table of the hamming function of every 16 bit integer, we can do the following to compute the Hamming weight of every 32 bit integer.

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.^[15] have shown that a vectorized version of popcount64b can run faster than dedicated instructions (e.g., popcnt on x64 processors).

Minimum weight[edit]

In error-correcting coding, the minimum Hamming weight, commonly referred to as the minimum weight w_min of a code is the weight of the lowest-weight non-zero code word. The weight w of a code word is the number of 1s in the word. For example, the word 11001010 has a weight of 4.

In a linear block code the minimum weight is also the minimum Hamming distance (d_min) and defines the error correction capability of the code. If w_min = n, then d_min = n and the code will correct up to d_min/2 errors.^[16]

Language support[edit]

Some C compilers provide intrinsic functions that provide bit counting facilities. For example, GCC (since version 3.4 in April 2004) includes a builtin function __builtin_popcount that will use a processor instruction if available or an efficient library implementation otherwise.^[17] LLVM-GCC has included this function since version 1.5 in June 2005.^[18]

In the C++ Standard Library, the bit-array data structure bitset has a count() method that counts the number of bits that are set. In C++20, a new header <bit> was added, containing functions std::popcount and std::has_single_bit, taking arguments of unsigned integer types.

In Java, the growable bit-array data structure BitSet has a BitSet.cardinality() method that counts the number of bits that are set. In addition, there are Integer.bitCount(int) and Long.bitCount(long) functions to count bits in primitive 32-bit and 64-bit integers, respectively. Also, the BigInteger arbitrary-precision integer class also has a BigInteger.bitCount() method that counts bits.

In Python, the int type has a bit_count() method to count the number of bits set. This functionality was introduced in Python 3.10, released in October 2021.^[19]

In Common Lisp, the function logcount, given a non-negative integer, returns the number of 1 bits. (For negative integers it returns the number of 0 bits in 2’s complement notation.) In either case the integer can be a BIGNUM.

Starting in GHC 7.4, the Haskell base package has a popCount function available on all types that are instances of the Bits class (available from the Data.Bits module).^[20]

MySQL version of SQL language provides BIT_COUNT() as a standard function.^[21]

Fortran 2008 has the standard, intrinsic, elemental function popcnt returning the number of nonzero bits within an integer (or integer array).^[22]

Some programmable scientific pocket calculators feature special commands to calculate the number of set bits, e.g. #B on the HP-16C^[3][23] and WP 43S,^[24][25] #BITS^[26][27] or BITSUM^[28][29] on HP-16C emulators, and nBITS on the WP 34S.^[30][31]

FreePascal implements popcnt since version 3.0.^[32]

Processor support[edit]

• The IBM STRETCH computer in the 1960s calculated the number of set bits as well as the number of leading zeros as a by-product of all logical operations.^[1]
• Cray supercomputers early on featured a population count machine instruction, rumoured to have been specifically requested by the U.S. government National Security Agency for cryptanalysis applications.^[1]
• Control Data Corporation’s (CDC) 6000 and Cyber 70/170 series machines included a population count instruction; in COMPASS, this instruction was coded as CXi.
• The 64-bit SPARC version 9 architecture defines a POPC instruction,^[12][1] but most implementations do not implement it, requiring it be emulated by the operating system.^[33]
• Donald Knuth’s model computer MMIX that is going to replace MIX in his book The Art of Computer Programming has an SADD instruction since 1999. SADD a,b,c counts all bits that are 1 in b and 0 in c and writes the result to a.
• Compaq’s Alpha 21264A, released in 1999, was the first Alpha series CPU design that had the count extension (CIX).
• Analog Devices’ Blackfin processors feature the ONES instruction to perform a 32-bit population count.^[34]
• AMD’s Barcelona architecture introduced the advanced bit manipulation (ABM) ISA introducing the POPCNT instruction as part of the SSE4a extensions in 2007.
• Intel Core processors introduced a POPCNT instruction with the SSE4.2 instruction set extension, first available in a Nehalem-based Core i7 processor, released in November 2008.
• The ARM architecture introduced the VCNT instruction as part of the Advanced SIMD (NEON) extensions.
• The RISC-V architecture introduced the PCNT instruction as part of the Bit Manipulation (B) extension.^[35]

See also[edit]

• Two’s complement
• Fan out

References[edit]

Further reading[edit]

• Schroeppel, Richard C.; Orman, Hilarie K. (1972-02-29). “compilation”. HAKMEM. By Beeler, Michael; Gosper, Ralph William; Schroeppel, Richard C. (report). Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA. MIT AI Memo 239. (Item 169: Population count assembly code for the PDP/6-10.)

External links[edit]

• 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 – by Damien Wintour – Has code in C# for various Hamming Weight implementations.
• Best algorithm to count the number of set bits in a 32-bit integer? – Stackoverflow

Вес Хэмминга из строки есть число символов, отличные от нулевого символа алфавита , используемым. Таким образом, это эквивалентно расстоянию Хэмминга от нулевой строки той же длины. Для наиболее типичного случая, строк биты , это число 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-битном целом числе? – Переполнение стека

Код на Ревью

function hammingWeight($weight)
{
    $array = str_split(decbin($weight));
    $amount = 0;
    foreach ($array as $value) {
        $amount += $value;
    }
    return $amount;
}

Контрольные точки

• Понятно ли с первого взгляда что делает функция (основываясь на содержимом)?
• Попробуйте воспроизвести определение понятия “Вес Хемминга” глядя только на код

Спецификация

Вес Хэмминга это количество единиц в двоичном представлении числа.
Реализуйте функцию hammingWeight, которая считает вес Хэмминга.

Проблемы

Ничего не говорящие и запутывающие имена переменных

Как известно, именование переменных, является одной из самых сложных задач в разработке и данный пример это подтверждает.
Плохие имена не только не помогают читать код, но и могут запутывать. В данном примере переменная $weight это, на самом деле,
исходное число, а вес это $amount.

Имя $array не запутывает, но и не помогает. Разумно, в данном случае, было назвать переменную $digits, что соответствует сути.

Алгоритм вычисления веса опирается не на спецификацию, а на корреляцию

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

Алгоритм опирается на особенности типизации в php

PHP обладает, так называемой, слабой типизацией. Это означает что php автоматически преобразует типы операндов в различных операциях,
вместо того чтобы сообщить об ошибке. Например при сложении числа со строкой. Слабая типизация это источник большого количества проблем
и странного поведения программы при определенных входных данных. Это относится не только к php, в javascript ситуация точно такая же.

Вывод

Функция выглядит магической и требует время на осознание. Перед тем как она будет понята, смотрящему придется увидеть указанную корреляцию.

Решение

Использовать реализацию основанную на определении понятия “вес Хемминга”.

function hammingWeight($num)
{
    $weight = 0;
    $digits = str_split(decbin($num));
    foreach ($digits as $value) {
        if ($value == '1') {
            $weight++;
        }
    }
    return $weight;
}

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

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

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

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

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

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

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

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

Здесь операции такие же, как в Язык программирования 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 м4  = 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 Икс){    Икс = (Икс & m1 ) + ((Икс >>  1) & m1 ); // помещаем количество каждых 2 бита в эти 2 бита     Икс = (Икс & m2 ) + ((Икс >>  2) & m2 ); // помещаем количество каждых 4 бита в эти 4 бита     Икс = (Икс & м4 ) + ((Икс >>  4) & м4 ); // помещаем количество каждых 8 бит в эти 8 бит     Икс = (Икс & m8 ) + ((Икс >>  8) & m8 ); // помещаем количество каждых 16 бит в эти 16 бит     Икс = (Икс & m16) + ((Икс >> 16) & m16); // помещаем количество каждых 32 бита в эти 32 бита     Икс = (Икс & m32) + ((Икс >> 32) & m32); // помещаем количество каждых 64 бит в эти 64 бита     возвращаться Икс;}// Здесь используется меньше арифметических операций, чем в любых других известных // реализация на машинах с медленным умножением.// Этот алгоритм использует 17 арифметических операций.int popcount64b(uint64_t Икс){    Икс -= (Икс >> 1) & m1;             // помещаем количество каждых 2 бита в эти 2 бита    Икс = (Икс & m2) + ((Икс >> 2) & m2); // помещаем количество каждых 4 бита в эти 4 бита     Икс = (Икс + (Икс >> 4)) & м4;        // помещаем количество каждых 8 бит в эти 8 бит     Икс += Икс >>  8;  // помещаем количество каждых 16 бит в самые младшие 8 бит    Икс += Икс >> 16;  // помещаем количество каждых 32 бита в самые младшие 8 бит    Икс += Икс >> 32;  // помещаем количество каждых 64 бит в самые младшие 8 бит    возвращаться Икс & 0x7f;}// Здесь используется меньше арифметических операций, чем в любых других известных // реализация на машинах с быстрым умножением.// Этот алгоритм использует 12 арифметических операций, одна из которых - умножение.int popcount64c(uint64_t Икс){    Икс -= (Икс >> 1) & m1;             // помещаем количество каждых 2 бита в эти 2 бита    Икс = (Икс & m2) + ((Икс >> 2) & m2); // помещаем количество каждых 4 бита в эти 4 бита     Икс = (Икс + (Икс >> 4)) & м4;        // помещаем количество каждых 8 бит в эти 8 бит     возвращаться (Икс * h01) >> 56;  // возвращает 8 левых битов x + (x << 8) + (x << 16) + (x << 24) + ... }

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

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

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

статический uint8_t биты слов[65536] = { / * количество битов целых чисел от 0 до 65 535 включительно * / };// Этот алгоритм использует 3 арифметических операции и 2 чтения из памяти.int popcount32e(uint32_t Икс){    возвращаться биты слов[Икс & 0xFFFF] + биты слов[Икс >> 16];}

// По желанию, таблица wordbits [] может быть заполнена с помощью этой функцииint popcount32e_init(пустота){    uint32_t я;    uint16_t Икс;    int считать;    за (я=0; я <= 0xFFFF; я++)    {        Икс = я;        за (считать=0; Икс; считать++) // заимствовано из popcount64d () выше            Икс &= Икс - 1;        биты слов[я] = считать;    }}

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

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

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

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

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

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

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

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

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

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

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

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

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

• В IBM STRETCH компьютер в 1960-х рассчитывал количество установленных битов, а также количество ведущих нулей как побочный продукт всех логических операций.^[1]
• Cray суперкомпьютеры на раннем этапе показали подсчет населения машинная инструкция, по слухам, был специально запрошен правительством США Национальное Агенство Безопасности за криптоанализ Приложения.^[1]
• Некоторые из Корпорация Control Data (CDC) Cyber ​​70/170 серийные машины включали инструкцию подсчета населения; в КОМПАС, эта инструкция была закодирована как CXi.
• 64-битный SPARC архитектура версии 9 определяет POPC инструкция^[11][1] но большинство реализаций не реализуют его, требуя, чтобы операционная система эмулировала его.^[31]
• Дональд Кнут модель компьютера MMIX это заменит СМЕШИВАНИЕ в его книге Искусство программирования имеет SADD инструкция с 1999 года. САДД a, b, c считает все биты, которые равны 1 в b и 0 в c, и записывает результат в a.
• Compaq с Альфа 21264A, выпущенный в 1999 году, был первым процессором серии Alpha, который имел расширение count (CIX).
• Аналоговые устройства ‘ Blackfin процессоры оснащены ОДИН инструкция для выполнения 32-битного подсчета населения.^[32]
• AMD с Барселона архитектура представила расширенную обработку битов (ABM) ЭТО представляя POPCNT инструкция как часть SSE4a расширений в 2007 году.
• Intel Core процессоры представили POPCNT инструкция с SSE4.2 Набор инструкций расширение, впервые доступное в Nehalem -основан Core i7 процессор, выпущенный в ноябре 2008 года.
• В ARM архитектура представил VCNT инструкция как часть Расширенный SIMD (НЕОН ) расширения.
• В RISC-V архитектура представила PCNT инструкция как часть расширения Bit Manipulation (B).^[33]

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

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

Рекомендации

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

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

внешняя ссылка

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