Loading article…
文字列の ハミング重みは、使用されているアルファベットのゼロ記号と異なる記号の数です。したがって、同じ長さのすべてゼロの文字列からのハミング距離に相当します。最も一般的なケースである、与えられたビットのセットの場合、これは 1 に設定されているビットの数、または与えられた数のバイナリ表現とビットベクトルのℓ ₁ ノルムの桁の合計です。このバイナリの場合、これは人口カウント[ 1 ]、popcount、サイドウェイズ サム[ 2 ]、またはビット加算[ 3 ]とも呼ばれます。
ハミング重みは、アメリカの数学者リチャード・ハミングにちなんで名付けられましたが、彼がこの概念を考案したわけではありません。[ 5 ] 2進数のハミング重みは、1899年にジェームズ・W・L・グレイシャーによって、パスカルの三角形の1行にある奇数2項係数の数の公式を与えるために既に使用されていました。[ 6 ]アービング・S・リードは、 1954年に2進数の場合のハミング重みに相当する概念を導入しました。[ 7 ]
ハミング重みは、情報理論、符号理論、暗号理論など、いくつかの分野で使用されています。ハミング重みの応用例としては、以下のようなものがあります。
ビット列の要素数は、暗号化やその他のアプリケーションでよく必要とされます。2つの単語AとBのハミング距離は、 A xor Bのハミング重みとして計算できます。[ 1 ]
効率的な実装方法については、これまで広く研究されてきました。一部のプロセッサでは、計算のための単一の演算、またはビットベクトルに対する並列演算が可能です。これらの機能を持たないプロセッサの場合、既知の最良の解決策は、ツリーパターンでカウントを加算することに基づいています。たとえば、16ビットのバイナリ数 a = 0110 1100 1011 1010 における 1 ビットの数をカウントするには、次の演算を実行できます。
ここでの操作はC プログラミング言語と同様で、 はX >> YX を Y ビット右にシフトすることを意味し、X & Y は X と Y のビットごとの AND を意味し、+ は通常の加算を意味します。この問題に対して知られている最良のアルゴリズムは、上記の概念に基づいており、ここに示されています: [ 1 ]
//以下の関数で使用される型と定数//uint64_t は、符号なし 64 ビット整数変数型です (C 言語の C99 バージョンで定義されています) const uint64_t m1 = 0x5555555555555555 ; //バイナリ: 0101... const uint64_t m2 = 0x3333333333333333 ; //バイナリ: 00110011.. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f ; //バイナリ: 4 つのゼロ、4 つの 1 ... const uint64_t m8 = 0x00ff00ff00ff00ff ; //バイナリ: 8 つのゼロ、8 つの 1 ... const uint64_t m16 = 0x0000ffff0000ffff ; //バイナリ: 16 個のゼロ、16 個の 1 ... const uint64_t m32 = 0x00000000ffffffff ; //バイナリ: 32 個のゼロ、32 個の1 const uint64_t h01 = 0x0101010101010101 ; //256 の 0、1、2、3 乗の合計...//これは比較のために示された素朴な実装であり、//より良い関数を理解するのに役立ちます。//このアルゴリズムは 24 の算術演算 (シフト、加算、および) を使用します。int popcount64a ( uint64_t x ) { x = ( x & m1 ) + (( x >> 1 ) & m1 ); //各 2 ビットのカウントをそれらの 2 ビットに格納しますx = ( x & m2 ) + (( x >> 2 ) & m2 ); //各 4 ビットのカウントをそれらの 4 ビットに格納しますx = ( x & m4 ) + (( x >> 4 ) & m4 ); //各 8 ビットのカウントをそれらの 8 ビットに格納しますx = ( x & m8 ) + (( x >> 8 ) & m8 ); //各 16 ビットのカウントをそれらの 16 ビットに格納しますx = ( x & m16 ) + (( x >> 16 ) & m16 ); // 32ビットごとのカウントをその32ビットに格納するx = ( x & m32 ) + (( x >> 32 ) & m32 ); // 64ビットごとのカウントをその64ビットに格納するreturn x ; }//これは、乗算が遅いマシン上での既知の実装の中で、最も少ない算術演算を使用します 。 //このアルゴリズムは17回の算術演算を使用します。int popcount64b ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; //各2ビットのカウントをその2ビットに格納x = ( x & m2 ) + (( x >> 2 ) & m2 ); //各4ビットのカウントをその4ビットに格納x = ( x + ( x >> 4 )) & m4 ; //各8ビットのカウントをその8ビットに格納x += x >> 8 ; //各16ビットのカウントをその下位8ビットに格納x += x >> 16 ; //各32ビットのカウントをその下位8ビットに格納x += x >> 32 ; //各64ビットのカウントをその下位8ビットに格納return x & 0x7f ; }//これは、高速乗算機能を備えたマシン上での既知の実装の中で、最も少ない算術演算を使用します 。 //このアルゴリズムは12回の算術演算を使用し、そのうち1回は乗算です。int popcount64c ( uint64_t x ) { x -= ( x >> 1 ) & m1 ; //各2ビットのカウントをその2ビットに格納x = ( x & m2 ) + (( x >> 2 ) & m2 ); //各4ビットのカウントをその4ビットに格納x = ( x + ( x >> 4 )) & m4 ; //各8ビットのカウントをその8ビットに格納return ( x * h01 ) >> 56 ; //xの残りの8ビットを返す + (x<<8) + (x<<16) + (x<<24) + ... }上記の実装は、既知のアルゴリズムの中で最も優れた最悪ケース動作を実現しています。ただし、値に非ゼロビットが少ないと予想される場合は、これらのビットを一度に 1 つずつカウントするアルゴリズムを使用する方が効率的な場合があります。Wegner が 1960 年に説明したように、[ 14 ] xとx − 1 のビットごとの AND は、最下位の非ゼロビットをゼロにする点のみで x と異なります。1を引くと、最も右の 0 の列が 1 に変わり、最も右の 1 が 0 に変わります。x が元々 n ビットの 1 を持っていた場合、この操作をn 回繰り返すだけで、xはゼロになります。次の実装はこの原理に基づいています。
//xのほとんどのビットが0の場合、この方法の方が優れています。 //このアルゴリズムは、すべてのデータサイズで同じように動作します。//このアルゴリズムは、xの「1」ビットごとに3つの算術演算と1つの比較/分岐を使用します。int popcount64d ( uint64_t x ) { int count ; for ( count = 0 ; x ; count ++ ) x &= x - 1 ; return count ; }ここで注目すべきは、Popcount、FFS、CLZの間の密接な関係である。
より多くのメモリ使用量が許容される場合、上記の方法よりも高速にハミング重みを計算できます。メモリが無制限であれば、64ビット整数ごとにハミング重みの大きなルックアップテーブルを作成するだけで済みます。16ビット整数ごとにハミング関数のルックアップテーブルを保存できる場合は、次の方法で32ビット整数ごとにハミング重みを計算できます。
static uint8_t wordbits [ 65536 ] = { /* 0 から 65535 までの整数のビット数 */ }; // このアルゴリズムは 3 つの算術演算と 2 つのメモリ読み取りを使用します。int popcount32e ( uint32_t x ) { return wordbits [ x & 0xFFFF ] + wordbits [ x >> 16 ]; }//オプションとして、この関数を使用して wordbits[] テーブルを埋めることができます。int popcount32e_init ( void ) { uint32_t i ; uint16_t x ; int count ; for ( i = 0 ; i <= 0xFFFF ; i ++ ) { x = i ; for ( count = 0 ; x ; count ++ ) // 上記の popcount64d() から借用x &= x - 1 ; wordbits [ i ] = count ; } }再帰アルゴリズムはDonovan & Kernighan [ 15 ]で示されている。
/* i の重みは、i の最下位ビットにおいてのみi / 2 の重みと異なる可能性があります*/ int popcount32e_init ( void ) { int i ; for ( i = 1 ; sizeof wordbits / sizeof * wordbits > i ; ++ i ) wordbits [ i ] = wordbits [ i >> 1 ] + ( 1 & i ); }Mułaら[ 16 ]は、popcount64bのベクトル化バージョンが専用命令（例えば、x64プロセッサ上のpopcnt）よりも高速に実行できることを示した。
誤り訂正符号において、最小ハミング重み（一般に符号の最小重みw minと呼ばれる）は、最も重みの低い非ゼロ符号語の重みです。符号語の重みwは、その符号語に含まれる 1 の数です。例えば、符号語 11001010 の重みは 4 です。
線形ブロック符号では、最小重みは最小ハミング距離（d min）でもあり、符号の誤り訂正能力を定義します。w min = n の場合、 d min = n となり、符号はd min /2 までの誤りを訂正します。[ 19 ]
C コンパイラの中には、ビットカウント機能を提供する組み込み関数を備えているものがあります。例えば、GCC (2004 年 4 月のバージョン 3.4 以降) には、__builtin_popcount利用可能な場合はプロセッサ命令を、そうでない場合は効率的なライブラリ実装を使用する組み込み関数が含まれています。[ 20 ] LLVM-GCC は、 2005 年 6 月のバージョン 1.5 以降、この関数を含んでいます。[ 21 ]
C++標準ライブラリでは、ビット配列データ構造に、セットされているビット数をカウントするメソッドがbitsetあります。C ++20では、符号なし整数型の引数を取る関数とを含む新しいヘッダーが追加されました。count()<bit>std::popcountstd::has_single_bit
Javaでは、拡張可能なビット配列データ構造に、セットされているビット数をカウントするメソッドがBitSetあります。さらに、プリミティブな32ビット整数と64ビット整数のビット数をそれぞれカウントする関数と関数があります。また、任意精度整数クラスにもビット数をカウントするメソッドがあります。BitSet.cardinality()Integer.bitCount(int)Long.bitCount(long)BigIntegerBigInteger.bitCount()
Pythonでは、このint型にbit_count()はセットされているビット数をカウントするメソッドがあります。この機能は、2021 年 10 月にリリースされた Python 3.10 で導入されました。[ 22 ]
Common Lispでは、logcount非負の整数が与えられた場合、関数は1 ビットの数を返します。（負の整数の場合は、2 の補数表記で 0 ビットの数を返します。）どちらの場合も、整数はbignumです。
GHC 7.4以降、 Haskell基本パッケージには、クラスpopCountのインスタンスであるすべての型で使用できる関数がありますBits（モジュールから利用可能ですData.Bits）。[ 23 ]
MySQL版SQL言語はBIT_COUNT()標準機能として提供されています。[ 24 ]
Fortran 2008 にpopcntは、整数 (または整数配列) 内の非ゼロビット数を返す標準の組み込み基本関数があります。 [ 25 ]
プログラム可能な科学用ポケット電卓の中には、セットビット数を計算するための特別なコマンドを備えているものもある。例えば、HP-16C#Bなどである。[ 3 ]
FreePascalはバージョン3.0以降、popcntを実装しています。[ 26 ]
CXi。POPC命令を定義しているが[ 12 ] [ 1 ]、ほとんどの実装ではそれを実装していないため、オペレーティングシステムによるエミュレーションが必要となる[ 27 ] 。SADDSADD a,b,cCIX）を備えた最初のAlphaシリーズCPU設計でした。ONES、32ビットの個体数カウントを実行する命令が搭載されています。[ 28 ]POPCNTPOPCNT拡張機能を持つ命令を導入しました。これは、2008年11月に発売されたNehalemベースのCore i7プロセッサで初めて利用可能になりました。VCNT ）拡張機能の一部として導入されました。CPOPアーキテクチャでは、ビット操作（B）拡張機能の一部としてこの命令が導入されました。 [ 29 ]ノードからクエリまでの距離のバイナリ表現における1の数になります。"