ハミングウェイト

文字列の ハミング重みは、使用されているアルファベットのゼロ記号と異なる記号の数です。したがって、これは同じ長さのすべてゼロの文字列からのハミング距離に相当します。最も一般的なケースであるビットの文字列の場合、これは文字列内の 1 の数、または指定された数のバイナリ表現とビットベクトルのℓ ₁ ノルムの桁合計です。このバイナリの場合、これは人口カウント、^[1]、ポップカウント、横方向合計、^[2]、またはビット合計とも呼ばれます。^[3]

ハミング重みはアメリカの数学者リチャード・ハミングにちなんで名付けられましたが、この概念を最初に考案したのはハミングではありません。^[5] 2進数のハミング重みは、1899年にジェームズ・WL・グレイシャーによってパスカルの三角形の1行に含まれる奇数の2項係数の数を表す式を与えるためにすでに使用されていました。^[6]アーヴィング・S・リードは、 2進数の場合のハミング重みに相当する概念を1954年に導入しました。^[7]

ハミング重みは、情報理論、符号理論、暗号化など、さまざまな分野で使用されています。ハミング重みの応用例には、次のようなものがあります。

• を二乗するモジュラー指数法では、指数eに必要なモジュラー乗算の回数はlog ₂ e + weight( e )である。これが、 RSAで使用される公開鍵の値eが通常、ハミング重みが低い数に選択される理由である。 ^[8]
• ハミング重みは、Chord分散ハッシュテーブル内のノード間のパスの長さを決定します。^[9]
• 生体認証データベースでのIrisCode検索は、通常、保存されている各レコードへのハミング距離を計算することによって実装されます。
• ビットボード表現を使用するコンピュータ チェスプログラムでは、ビットボードのハミング重みは、ゲームに残っている特定の種類の駒の数、または 1 人のプレーヤーの駒によって制御されるボードのマス目数を示すため、位置の値に重要な影響を与える用語です。
• ハミング重みは、 ffs(x) = pop(x ^ (x - 1))という恒等式を使用して、find first setを効率的に計算するために使用できます。これは、ハードウェアハミング重み命令はあるが、ハードウェアfind first set命令がないSPARCなどのプラットフォームで役立ちます。 ^{[10] [1]}
• ハミング重み演算は、一進数から二進数への変換として解釈できる。^[11]
• ビットベクトルやウェーブレットツリーなどの簡潔なデータ構造の実装。

暗号やその他のアプリケーションでは、ビット列の人口カウントが必要になることがよくあります。2つの単語AとBのハミング距離は、 A xor Bのハミング重みとして計算できます。^[1]

これを効率的に実装する方法の問題は、広く研究されてきました。一部のプロセッサでは、計算のための単一の操作、またはビット ベクトルの並列操作が可能です。これらの機能を備えていないプロセッサの場合、ツリー パターンでカウントを追加することが、最も優れたソリューションとして知られています。たとえば、16 ビットの 2 進数 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 = 0x333333333333333 ; // バイナリ: 00110011... const uint64_t m4 = 0x0f0f0f0f0f0f0f0f ; // バイナリ: 4 つのゼロ、4 つの 1... const uint64_t m8 = 0x00ff00ff00ff00ff ; // バイナリ: 0 が 8 個、1 が 8 個... const uint64_t m16 = 0x0000ffff0000ffff ; // バイナリ: 0 が 16 個、1 が 16 個... const uint64_t m32 = 0x00000000ffffffff ; // バイナリ: 0 が 32 個、1 が 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 = ( 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 年に説明したように、^[12] xとx − 1 のビット単位のAND は、最下位の非ゼロビットをゼロにする点のみがx と異なります。つまり、1 を引くと、右端の 0 の文字列が 1 に変わり、右端の 1 が 0 に変わります。xに元々 1 であるビットがn個あった場合、この操作を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 ; }  

     
       
            
     

より多くのメモリ使用量が許容される場合、上記の方法よりも速くハミング重みを計算できます。メモリが無制限であれば、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 ; } } 

     
     
     
         
    
          
            
                
          
    

Mułaら^[13]は、 popcount64bのベクトル化されたバージョンが専用命令（例えば、x64プロセッサ上のpopcnt）よりも高速に実行できることを示しました。

誤り訂正符号化では、最小ハミング重み（一般にコードの最小重み w _{minと呼ばれる）は、重みが最も小さい非ゼロのコード ワードの重みです。コード ワードの重み}wは、ワード内の 1 の数です。たとえば、ワード 11001010 の重みは 4 です。

線形ブロック符号では、_最小重みは最小ハミング距離（d _min）でもあり、符号の誤り訂正能力を定義します。w min = n の場合、  d  min = n となり、_符号 は 最大d _min /2個の誤りを訂正します。^[14]

一部のCコンパイラはビットカウント機能を提供する組み込み関数を提供しています。たとえば、GCC（2004年4月のバージョン3.4以降）には、__builtin_popcount利用可能な場合はプロセッサ命令を使用し、そうでない場合は効率的なライブラリ実装を使用する組み込み関数が含まれています。^[15] LLVM-GCCは、2005年6月のバージョン1.5以降、この関数を含んでいます。 ^[16]

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があります。この機能は、2021年10月にリリースされたPython 3.10で導入されました。 ^[17]bit_count()

Common Lispでは、関数 はlogcount、負でない整数を与えると、 1 のビットの数を返します。(負の整数の場合は、2 の補数表記で 0 のビットの数を返します。) どちらの場合でも、整数は BIGNUM にすることができます。

GHC 7.4以降、 Haskellベースパッケージには、クラスpopCountのインスタンスであるすべての型で使用できる関数が含まれていますBits（モジュールから利用可能Data.Bits）。^[18]

MySQLバージョンのSQL言語はBIT_COUNT()標準機能として提供されています。^[19]

Fortran 2008にpopcntは、整数（または整数配列）内の非ゼロビットの数を返す標準的な組み込み要素関数があります。 ^[20]

#B一部のプログラム可能な科学計算用ポケット電卓には、設定されたビットの数を計算するための特別なコマンドが搭載されている。例えば、HP-16C ^{[3] [21]}やWP 43S、^{[22] [23]} #BITS^{[24] [25]}またはBITSUM^{[26] [27]}のHP-16Cエミュレータ、およびWP 34S ^{[28] [29]}nBITSなどである。

FreePascalはバージョン3.0以降でpopcntを実装している。^[30]

• 1960年代のIBM STRETCHコンピュータは、すべての論理演算の副産物として、設定されたビットの数と先頭のゼロの数を計算しました。 ^[1]
• クレイ社のスーパーコンピュータは初期には人口カウントマシン命令を搭載していたが、これは米国政府の国家安全保障局が暗号解読アプリケーションのために特別に要求したものと噂されている。 ^[1]
• Control Data Corporation (CDC) の6000およびCyber​​ 70/170シリーズ マシンには、人口カウント命令が含まれていました。COMPASS では、この命令は としてコード化されていましたCXi。
• 64ビットSPARCバージョン9アーキテクチャではPOPC命令が定義されているが^{[10] [1]}、ほとんどの実装ではこれを実装しておらず、オペレーティングシステムでエミュレートする必要がある。^[31]
• ドナルド・クヌースの著書『The Art of Computer Programming』でMIXに代わるモデル コンピュータMMIX には、1999 年から命令があります。b で 1 で c で 0 であるすべてのビットをカウントし、その結果を a に書き込みます。SADDSADD a,b,c
• 1999 年にリリースされたCompaqのAlpha 21264A は、カウント拡張 ( CIX) を備えた最初の Alpha シリーズ CPU 設計でした。
• アナログ・デバイセズのBlackfinONESプロセッサは、32ビットの人口カウントを実行する命令を備えています。 ^[32]
• AMDのBarcelonaアーキテクチャでは、2007 年にSSE4a拡張の一部として命令を導入した高度なビット操作 (ABM) ISAが導入されました。POPCNT
• Intel Coreプロセッサでは、SSE4.2命令セットPOPCNT拡張を備えた命令が導入され、2008 年 11 月にリリースされたNehalemベースのCore i7プロセッサで初めて利用可能になりました。
• ARMアーキテクチャでは、Advanced SIMD ( NEONVCNT ) 拡張の一部としてこの命令が導入されました。
• RISC -VCPOPアーキテクチャでは、ビット操作（B）拡張の一部としてこの命令が導入されました。 ^[33]

• 2の補数
• ファンアウト

• Schroeppel, Richard C. ; Orman, Hilarie K. (1972-02-29)。「コンパイル」。HAKMEM。Beeler , Michael、Gosper, Ralph William、Schroeppel, Richard C. (レポート) 著。人工知能研究所、マサチューセッツ工科大学、マサチューセッツ州ケンブリッジ、米国。MIT AI メモ 239。(項目 169: PDP/6-10 の人口カウント アセンブリ コード)

• 集計マジック アルゴリズム。最適化された人口カウントとその他のアルゴリズムをサンプル コードで説明します。
• ビット操作ハック ビットをカウントするためのコードが設定されたいくつかのアルゴリズム。
• 必要かつ十分 2017-09-23 にWayback Machineにアーカイブ- Damien Wintour 著 - さまざまなハミング重み実装の C# コードが含まれています。
• 32 ビット整数内のセット ビットの数をカウントする最適なアルゴリズムはどれですか? - Stackoverflow