17

それで、ビット操作に関して以前にインタビューの質問がありました。同社は有名なGPU企業です。私はアセンブリ言語のバックグラウンドがほとんどなく (コンピューター アーキテクチャの博士課程の学生であるにもかかわらず)、この話が示すように、失敗しました。質問は簡単でした：

「32 ビット レジスタの 1 の数をカウントする高速なコードを記述してください。」

現在、アームの組み立てを勉強中です。当然のことながら、私はこの問題に再び立ち返り、ISA を勉強するだけでこのコードを思いつきました。

あなたがそこにいる専門家を武装させるために、これは正しいですか？これを行うより速い方法はありますか？初心者なので当然不完全だと思います。「xx」の AND 命令は冗長に感じますが、ARM でレジスタをシフトする方法は他にありません...

R1 には最後にビット数が含まれ、R2 はカウントしたいビットを含むレジスタです。r6 は単なるダミーレジスタです。コメントは () で囲みます。

    MOV   R1, #0                (initialize R1 and R6 to zero)
    MOV   R6, #0        
xx: AND   R6, R6, R2, LSR #1    (Right shift by 1, right most bit is in carry flag)
    ADDCS R1, #1                (Add #1 to R1 if carry  flag is set)
    CMP R2, #0                  (update the status flags if R2 == 0 or not)
    BEQ xx                      (branch back to xx until R2==0)
4

6 に答える 6

7

ビットハックの最良の参考文献は

Bit Twiddling Hacksページは言う

The best method for counting bits in a 32-bit
integer v is the following:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

gcc次に、and objdump(またはこの優れたオンライン gcc ツール) を使用して、この高レベルのスニペットがアーム命令としてどのように見えるかを確認することをお勧めします。

00000000 <popcount>:
 0: 1043        asrs    r3, r0, #1
 2: f003 3355   and.w   r3, r3, #1431655765 ; 0x55555555
 6: 1ac0        subs    r0, r0, r3
 8: 1083        asrs    r3, r0, #2
 a: f000 3033   and.w   r0, r0, #858993459  ; 0x33333333
 e: f003 3333   and.w   r3, r3, #858993459  ; 0x33333333
12: 18c0        adds    r0, r0, r3
14: eb00 1010   add.w   r0, r0, r0, lsr #4
18: f000 300f   and.w   r0, r0, #252645135  ; 0xf0f0f0f
1c: eb00 2000   add.w   r0, r0, r0, lsl #8
20: eb00 4000   add.w   r0, r0, r0, lsl #16
24: 1600        asrs    r0, r0, #24
26: 4770        bx  lr

したがって、これにより命令が得られるように見えますが12、これはおおよそ同じ量のサイクルに変換できます。

上記の整数操作をlibgcclook up tableで使用されるアプローチと比較すると、ルックアップ テーブルは余分なメモリ アクセスを考慮するとさらに遅くなるはずです。

00000028 <__popcountSI2>:
28: b410        push    {r4}
2a: 2200        movs    r2, #0
2c: 4c06        ldr r4, [pc, #24]   ; (48 <__popcountSI2+0x20>)
2e: 4613        mov r3, r2
30: fa40 f103   asr.w   r1, r0, r3
34: 3308        adds    r3, #8
36: 2b20        cmp r3, #32
38: b2c9        uxtb    r1, r1
3a: 5c61        ldrb    r1, [r4, r1]
3c: 440a        add r2, r1
3e: d1f7        bne.n   30 <__popcountSI2+0x8>
40: 4610        mov r0, r2
42: bc10        pop {r4}
44: 4770        bx  lr
46: bf00        nop
48: 00000000    andeq   r0, r0, r0
<.. snipped ..>
于 2013-04-01T08:43:52.307 に答える
7

これは ARM とタグ付けされているため、このclz命令が最も役に立ちます。この問題は人口数とも呼ばれます。gccこれには__builtin_popcount()があります。ARM ツールも同様です。このリンクがあります (あなたのソリューションについて悪く思わないでください。誰かがほぼ同じ Web ページを作成しました) 。また、非ARM用の 6 つの命令を含むDave Seal のバージョンもあります。clzこれclz は有利であり、入力によってはより高速なアルゴリズムを生成するために使用できます。

auselen の良い読書の提案と同様に、 Hacker's Delightこのちょっといじくり回しブログは、グラフィックのコンテキストでそのようなことについて話しているので、役立つかもしれません。少なくとも、Qt のブリッティング コードの一部を理解することは役に立ちました。ただし、人口カウントルーチンのコーディングにはある程度の有用性があります。

ユニットは分割統治のcarry add意味で役立ち、問題を引き起こしO(ln n)ます。 データに連続する1または0clzがある場合は、より便利です。

Hacker's Delight のエントリでは、Dave Seal の ARM コードに関する背景が詳しく説明されています。

于 2013-04-01T13:17:53.003 に答える
2 
    LDR r0, = 0x000000FF;
    MOV r1, #0;
    MOV r3, #0; this will always be zero
    MOV r2,r0;
rep MOVS r2, r2, LSR #1;
    ADC r1,r1, r3;  this adds r1 with zero plus the carry bit
    CMP r2, #0;
    BNE rep

This will do it, r3 is just a dummy register with 0 to make ADC work properly.

于 2016-04-26T21:04:40.790 に答える