17

所以我之前有一个关于位操作的面试问题。该公司是一家知名的 GPU 公司。我在汇编语言方面的背景很少（尽管我是计算机体系结构的博士生，但很奇怪），正如这个叙述所表明的那样，我搞砸了。问题很简单：

“编写一个快速代码，计算 32 位寄存器中 1 的数量。”

现在我正在研究手臂组装。所以很自然地，我再次重新审视了这个问题，并通过研究 ISA 得出了这段代码。

对于您那里的武装专家，这是正确的吗？有没有更快的方法来做到这一点？作为初学者，我自然认为这是不完整的。“xx”中的 AND 指令感觉是多余的，但没有其他方法可以在 ARM isa 中移动寄存器...

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

12

此代码是否快速取决于处理器。可以肯定的是，它在 Cortex-A8 上不会很快，但在 Cortex-A9 和更新的 CPU 上可能会运行得非常快。

然而，这是一个非常简短的解决方案。

期望 r0 中的输入，并在 r0 中返回输出

  vmov.32 d0[0], r0
  vcnt.8  d0, d0
  vmov.32 r0, d0[0]

  add r0, r0, r0, lsr #16
  add r0, r0, r0, lsr #8
  and r0, r0, #31

主要工作在vcnt.8 指令中完成，该指令对 NEON 寄存器中每个字节的位进行计数，并将位计数存储回 D0 的字节中。

没有vcnt.32形式，只有.8，所以你需要将 4 个字节水平相加，这就是其余代码正在做的事情。

于 2013-04-01T09:52:24.677 回答
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

然后我建议你使用gccand objdump（或这个很棒的在线 gcc 工具）来看看这个高级代码片段看起来像 arm 指令。

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 工具也是如此。有这个链接（不要对您的解决方案感到难过，有人制作了一个几乎相同的网页），还有Dave Seal 的版本，其中包含针对非clzARM 的六条指令。这clz 是有利的，可用于产生更快的算法，具体取决于输入。

除了auselen 的良好阅读建议之外，Hacker's Delight这个有趣的博客可能会有所帮助，它在图形上下文中讨论此类事情。至少我发现理解一些 Qt 的 blitting 代码很有用。但是，它在编写人口计数例程时有一些用处。

该carry add单元在分而治之的意义上很有用，从而解决了问题O(ln n)。 如果数据包含1或0clz则更有用。

Hacker's Delight条目有更多关于 Dave Seal 的 ARM 代码的背景。

于 2013-04-01T13:17:53.003 回答
5

您可以使用预先计算的查找表并将迭代次数减少到 2 或 4。

您也可以使用对数方法。

有关详细信息，请参阅此 Wikipedia 文章。

于 2013-04-01T02:01:42.157 回答
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

这样就可以了，r3 只是一个带有 0 的虚拟寄存器，以使 ADC 正常工作。

于 2016-04-26T21:04:40.790 回答
2

long count_bits_long（长）；

    vmov.32 d0[0], r0       // R0 --> SIMD

    vcnt.8  d0, d0          // count bits in bytes
    vpaddl.u8 d0, d0        // add adjacent pairs of bytes and put into 16b words
    vpaddl.u16 d0, d0       // add adjacent pairs of 16b words and put into 32b word

    vmov.32 r0, d0[0]       // SIMD --> R0

    mov pc, lr              // return
于 2017-10-08T17:50:57.940 回答