私は32ビットの数値を持っていて、1ビットの数を数えたいと思っています。
私はこの擬似コードについて考えています：
mov eax, [number]
while(eax != 0)
{
div eax, 2
if(edx == 1)
{
ecx++;
}
shr eax, 1
}
より効率的な方法はありますか？
x86プロセッサでNASMを使用しています。
（私はアセンブラーを始めたばかりなので、externライブラリのコードを使用するように言わないでください。それらを含める方法すらわからないからです;））
（ 32ビット整数のセットビット数を数える方法を見つけましたか？これには私の解決策も含まれています。他の解決策も投稿されていますが、残念ながら、アセンブラーでそれらをどのように書くかがわかりません）
（とにかく実行時間の観点から）最も効率的な方法は、ルックアップテーブルを用意することです。明らかに、40億のエントリテーブルはありませんが、32ビットを8ビットチャンクに分割して256エントリのテーブルのみが必要な場合もあれば、さらに4ビットチャンクに分割して16エントリのみが必要な場合もあります。 。幸運を！
SSE4をサポートするプロセッサには、これを行うPOPCNT命令があります。
最も素朴なアルゴリズムは、実際にはあなたが思っていたよりも高速です（DIV命令は本当に遅いです）。
mov eax, [number]
xor ecx,ecx
loop_start:
test eax,1
jnz next
inc ecx
next:
shr eax, 1
mov eax,ecx
以前のSO回答についてのコメントについては、そこから回答例を取り上げて、変換方法について説明します。
long count_bits(long n) {
unsigned int c; // c accumulates the total bits set in v
for (c = 0; n; c++)
n &= n - 1; // clear the least significant bit set
return c;
}
（私はあなたが関数とそのような楽しいものを定義する方法を知っていると仮定します）。必要なのは、非常に単純なループ、カウンター変数（従来、ecxはインデックスとカウンターの両方です）、およびビットテスト命令です。
mov edx,n
xor ecx,ecx
loop_start:
test edx,edx
jz end
mov ebx,edx
dec ebx
and edx,ebx
inc ecx
jmp loop_start
end:
mov eax,ecx
ret
アセンブリにハミング重みアルゴリズムのようなものを実装することは複雑ではありませんが、最初の宿題の問題としてそれを実行したくないほど複雑です。
私のx86アセンブラは少し錆びていますが、これが思い浮かびます。
clc ; clear carry
xor ecx, ecx ; clear ecx
shl eax, 1 ; shift off one bit into carry
adc ecx, 0 ; add carry flag to ecx
; ... repeat the last two opcodes 31 more times
ecxビット数が含まれます。
CFシフトアウトされた最後のビットに設定されたx86シフト命令adc ecx, 0。
ちなみに、優れたパフォーマンスが必要な場合は、通常、8ビットテーブルルックアップまたは乗算ビットハック（GCCの現在のスカラーフォールバック__builtin_popcntなし-mpopcnt）を使用して、ループ/分岐を回避する必要があります。数値が通常小さい場合（1だけ右シフト）、または数値に通常数ビットしか設定されていない場合（で最下位の設定ビットをクリアするときにループするx & (x-1)）、ループはほとんど問題ありません。ただし、ビットの半分以上が設定されている数値の場合、パフォーマンスはかなり低くなります。
最新のx86CPUのほとんどは、popcnt命令をサポートしています。これはSSE4.2によって暗示されますが、独自のCPUID機能ビットも備えているため、CPUはSSE4.2なしでそれを使用できます。IntelCore2以前にはこれがありません。
xor eax,eax ; avoid false dependency on Sandybridge-family before IceLake
popcnt eax, edi
たとえば、同じレジスタを上書きしてもかまわない場合popcnt edi, ediは、出力の誤った依存関係の危険性を回避できます。同じレジスタにすでに真の依存関係があります。（LZCNTの「出力依存関係」を破ることが重要なのはなぜですか？）
HWがない場合popcnt、別のオプションはSSSE3です。これはpshufb、特にAVX2を使用している場合に、大きなアレイをカウントするのに実際に最適です。見る
movzx ecx, al配列ルックアップが可能で、各バイトを//などで抽出します。次にmovzx edx, ah/ 。合計結果は最大64になるため、8ビットレジスタをオーバーフローさせないことに注意してください。良好なパフォーマンスを得るには、キャッシュ内でホット状態を維持するために256バイトのテーブルが必要になります。多くのpopcntを実行するが、SIMDを使用できない場合は、これは良い選択かもしれません。ユースケースのビットハックに対してベンチマークします。shr eax, 16movzx ecx, [table + rcx]add cl, [table + rdx]
https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallelからのビットハック/ 32ビット整数のセットビット数をカウントする方法は？コンパイル時にHWpopcntが有効になっていない場合、GCCが現在使用しているものです。（つまり、libgccヘルパー関数内）。ビットハックがビットを2ビットアキュムレータに合計し、次に水平方向に4ビットに合計する方法/理由の説明については、その回答を参照してください（面白い事実：GCCとclangは、実際にはCロジックをpopcntイディオムとして認識し、コンパイルします次のasmは-mpopcntなしのpopcntGCC - O3出力です。手作業で改善する方法はありません。可能な限りEAXを宛先として使用し、ANDを使用してmodrmなしで短い形式を許可します。バイト。）-mpopcnt and eax, imm32
この非分岐コードはデータルックアップを必要としないため、キャッシュミス（Iキャッシュを除く）を行うことはできません。ポップカウントのパフォーマンス（特にレイテンシー）を気にする場合はおそらく良いでしょうが、頻繁には実行しないでください。ルックアップテーブルをキャッシュ内でホットに保つのに十分です。（または64ビット整数の場合、これの64ビットバージョンはおそらく8xバイトルックアップよりも優れています。）
; x86-64 System V calling convention
; but also of course works for 32-bit mode with the arg in a register
numberOfSetBits: ; 32-bit unsigned int x in EDI
mov eax, edi
shr eax, 1
and eax, 0x55555555 ; (x>>1) & 0x55555555
sub edi, eax ; x -= ((x>>1) & 0x55555555) 2-bit sums
mov eax, edi
shr edi, 0x2
and eax, 0x33333333
and edi, 0x33333333
add edi, eax ; pairs of 2-bit accumulators -> 4
mov eax, edi
shr eax, 0x4
add eax, edi ; we can add before masking this time without overflow risk
and eax, 0x0f0f0f0f
imul eax, eax, 0x01010101 ; sum the 4 bytes into the high byte (because their values are small enough)
shr eax, 24
ret
64ビット整数の場合、これは同じシーケンスであり、64ビット乗算で終わります。（ただし、64ビットのマスク定数と乗数定数を実体化する必要がありmov reg, imm64ます。これらはANDまたはIMULの即時として機能しません）。
RORXのような命令は、mov / shrの代わりにコピーアンドシフトをより効率的に行うのに役立つ可能性がありますが、RORXを搭載したCPUにもPOPCNTが搭載されているため、これを使用する必要があります。LEAからコピーアンドレフトシフトは役に立ちません。加算はキャリーをローからハイに伝播するため、最初のステップでトップのビットが失われないようにするには、右シフトする必要があります。この>>2ステップは、2ビットアキュムレータの各ペアの上位にも追加できませんでした。その時点での最大合計は4であり、表現するには3ビットが必要であるため、（レジスタの最上位にある）最も高いアキュムレータが失われる可能性があります。あなたがした場合のカウントlea eax, [rdi + rdi]/2xおよび/add、4ビットがずれているのではなく、2つしかないため、最終的には、imulの前のある時点でカウンターをバイトの下部に戻すために右シフトが必要になるため、クリティカルを長くします。前の手順で左シフト/追加を使用できた場合でも、パスの待ち時間。
3つの主な選択肢があります。
add same,sameまたは右shr）、シフトアウトされたビットを追加します。セットビットが通常ハイエンドまたはローエンドに向かってクラスター化され、32回の反復よりはるかに少ない後にレジスタがゼロになる場合はそれほど悪くありませんが、それでも最悪のケースです。x &= x-1ゼロになるまでの反復回数をカウントします。セットビットの合計が少ない場合は、それほど悪くありません。（または、最初に入力を行わない場合、クリアされたビットが少ない場合。または、ゼロに設定された最小ビットを設定するためのビットハックがある場合がありますx |= x+1か？）最悪の場合はまだ32回の反復であり、単にシフトするよりも長いdepチェーンがあります。コードサイズが小さい（速度ではない）場合、ハミング重み（数値の1）で示されるループは、 Cとアセンブリを混合するのに非常に適しています。そのNASMバージョンは次のようになります。
;;; Good for small inputs (all set bits near the bottom)
;; input: EDI (zeroed when we're done)
;; output: EAX = popcnt(EDI)
popcount_shr_loop:
xor eax, eax
; optional: make the first adc non-redundant by peeling the first iteration. Otherwise just fall into the loop (with CF=0 from xor)
shr edi, 1 ; shift low bit into CF
;; jz .done ; not worth running an extra instruction for every case to skip the loop body only for the input == 0 or 1 case
.loop:
adc eax, 0 ; add CF (0 or 1) to result
shr edi, 1
jnz .loop ; leave the loop after shifting out the last bit
;.done:
adc eax, 0 ; and add that last bit
ret
入力の設定ビットが上部に近い可能性が高い場合は、代わりにを使用します。add edi, ediこれshrは、 FLAGSを設定するため、同じように処理shlします。 Sandybridgeファミリーでaddマクロ融合できるので、実際には;よりもわずかに優れています。ハイパースレッディングに対応し、ROB内のuopsが少ないため、loop-exitブランチが正しく予測されていれば、OoOexecはそれをはるかに超えて見ることができます。または、以前のキャッシュミスや何かがまだリタイアメントを失速させている場合は、より早くループに入ります。jccshr
さらに小さいコードサイズの場合はshr、ループに入る前にスキップできるため、最初のコードadcは冗長です。（xor-zeroingはCFをクリアします）。
@spoulsonの回答は、ループを32回展開することを提案しています（jz .doneなし）。任意のビットパターンで最大速度を実現するために、1つの大きな直線ブロックのコードが必要な場合は、乗算で終わるビットハックシフト/および/追加の方が適しています。 adc reg,0Intel P6ファミリ（PProからNehalem）を除くほとんどのCPUで1 uopです（Broadwell以前のIntel SnBファミリの特殊なケース0でした）。とにかく、64 uopsと32サイクルのレイテンシーは、15 uopのビットハックと比べてまだ悪いので、これを完全に展開すると、他の戦略よりも悪くなります。
ただし、これを2または4ずつ展開することは、中途半端なものとして意味があります。これにより、異なる入力が同じように分岐します。たとえば、下位4に設定されたビットを持つすべての入力は、分岐が行われずにループを1回実行します。
popcount_shr_loop_unroll2:
xor eax, eax
shr edi, 1 ; shift low bit into CF
;; jz .done ; still optional, but saves more work in the input <= 1 case. Still not worth it unless you expect that to be very common.
.loop:
%rep 2 ;; Unroll
adc eax, 0 ; add CF (0 or 1) to result
shr edi, 1
%endrep ;; still ending with ZF and CF set from a shift
jnz .loop ; leave the loop on EDI == 0
;.done:
adc eax, 0 ; there may still be a bit we haven't added yet
ret
/をループ分岐として実行することにより、アウトオブオーダーexecにループ終了条件をより早く認識させ、ループ本体にEDIを別のレジスタにコピーさせ、一度に下位4ビットをシフトアウトさせることができます。しかし、その時点では、おそらくビットハックバージョンが必要です。OoOexecを搭載したx86CPUは、Pentium II / IIIでは4サイクルのレイテンシ、AMD K8以降では3サイクル、Core 2以降はIntelのように、高速のimul r32を備えています。また、コードのフェッチ/デコード機能は、32を含むより大きな命令を処理する必要があります。 -ビットマスク定数は十分です。shr edi, 4jnz
（古いCPUを検討しているため：P5 Pentiumで、shr両方ともUパイプでのみ実行できるため、展開してもILPadcを利用するために互いにペアリングすることはできません。ただし、 UパイプまたはVパイプのいずれかで実行できるaddため、CRに変換されます。）add
もう1つの展開オプションは、2つに分割することです。上半分が上から出て、下半分が下から出ます。（レイテンシーを気にする場合は、別々のカウンターに蓄積します。そうしないと、OoO execがループの終了をより早く見つけるのに役立ちます。しかし、両方の半分がゼロであるかどうかのテストは不格好になります。多分//。ADDmov ecx, ebxはjnzとマクロ融合できます。 ORとは異なり、SnBファミリ。または、LEA / TEST + JNZ、AMD ZenおよびIntelの2つのフロントエンドuopsを使用します。）add ecx, edxjnz
もう1つのオプションは、lea edx, [rdi-1]/をループすることですand edi, edx（最下位のセットビットをクリアし、ゼロになった場合はZFをセットします）。これは、数ビットしか設定されていない数値でも問題ありません。
;; could be good if very few bits are set, even if they're scattered around
;; Input: EDI (zeroed when done)
;; output: EAX = popcount(EDI)
;; clobbers: EDX
popcount_loop_lsr:
xor eax,eax
test edi,edi
jz .done ; if(!x) return 0;
.loop: ; do{
inc eax ; ++count
lea edx, [rdi-1]
and edi, edx ; x &= x-1 clear lowest set bit
jnz .loop ; }while(x)
.done:
ret
のようなその他のビットハックについては、 https： //catonmat.net/low-level-bit-hacksx & (x-1)を参照してください。また、BMI1命令がこれを行うことに注意してください。これは、x86命令リファレンスを既に開いている場合に、数式を思い出させるために確認するのに便利な場所です。しかしもちろん、BMI1があれば、。popcntには実際には独自の機能ビットがありますが、BMI1はあるがpopcnt/SSE4.2がない実際のCPUはありません。blsrpopcnt
他のループのSHRとADC（シングルuop ADCを想定）を介した1サイクルの依存関係とは異なり、これにはLEAとANDを介した2サイクルのループ伝達依存関係があることに注意してください。したがって、各反復には2倍のデータ依存関係があります。しかし、プラス面としては、ゼロを超えてスキップして、設定されたビットをループするだけです。それでも、最悪の場合（EDI=-1）には2倍の遅延があります。
and/jnz実際には、IntelSnBファミリでマクロ融合して単一のブランチuopにすることができます。（のようなものだからtest）。したがって、反復ごとに3つのフロントエンドuopsしかありませんが、ブランチの誤予測がすぐに検出される可能性は低いため、全体的なフロントエンドコストの観点から、このバージョンは悪い可能性があります。
inc eaxループの反復をカウントするだけで、更新ロジックへのデータ依存性がないためx、ループの後に中間の一時がすでにゼロであるかどうかを確認するために追加のロジックを実行しない限り、展開にはブランチが必要になると思います。depチェーンはクリティカルパスであるためx &= x-1;、展開はおそらく役に立ちません。
（すべてのセットビットの位置を見つけて配列に格納する場合、別のQ＆Aでの@aqritの回答のように、ポップカウントする別の効率的な方法がある場合は、オーバーシュートで展開できます）
mov eax,[c]
xor ebx,ebx
SSS: shr eax,1 ; after shift, if eax=0 ZF flag=1
jz XXX ; end (no more bit on eax)
adc bl
jmp SSS
XXX: adc bl
movb [Nbit],bl
このプログラムは、32ビット数の1の数を提供します。試してみる ：）
extern printf
SECTION .data
msg: db "The number of 1 bits are: %d",10,0
inta1: dd 1234567
num: dd 2147483647
SECTION .text
global main
main:
mov eax, [num]
mov ecx,32
mov edx,0
.loop: dec ecx
cmp ecx,0
jl .exit
shr eax,1
jnc .loop
inc edx
jmp .loop
.exit:
push edx
push dword msg
call printf
add esp, 8
bsf（ビットスキャンフォワード）を使用すると、単純なシフトよりもおそらく少し効率的です。
xor edx,edx
mov eax,num
bsf ecx,eax
je end_bit_count
; align?
loop_bit_count:
inc ecx
inc edx
shr eax,cl
bsf ecx,eax
jne loop_bit_count
end_bit_count:
mov eax,dword [number]; we store the number in eax
mov ecx,1
mov edx,0
loop_1:
cmp eax,0 ;we compare the number with 0
je endl_loop ;when the number is zero we exit the loop
test eax,01h ;is the last bit equal to 1?
jpe the_bit_is_zero ;jump if parity is even=the bit is zero
inc edx ;we found another 1 digit
the_bit_is_zero:
inc ecx ;we continue the loop
shr eax,1 ;shift the bits to right =nr/2
loop loop_1
endl_loop:
;the result is stored in edx
一番いい方法：
tabx:array [0..255] of byte = //number of bit for each byte (COPY THIS TABLE)
(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8);
In MASM:
asm
mov eax,number //32 bit
movzx ecx,tabx[al] //for clear ecx except cl
addb cl,tabx[ah] //add ah to cl
shr eax,16 //put left part in ah-al
addb cl,tabx[al]
addb cl,tabx[ah]
mov result,ecx