关于位操作,我之前有一个面试问题.该公司是一家知名的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)
Nil*_*nck 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寄存器中每个字节的位,并将bitcount存储回D0的字节.
没有vcnt.32形式,.8所以你需要将4个字节水平地加在一起,这是其余代码所做的.
有关位黑客的最佳参考是
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和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 ..>
您可以使用预先计算的查找表,并将迭代次数减少到2或4.
您也可以使用对数方法.
有关更多信息,请参阅此Wikipedia文章.
由于此标签为ARM，因此该clz说明很有帮助。这个问题也被描述为人口数量。为此gcc具有__builtin_popcount（）。和ARM工具一样。有这个链接（不要为您的解决方案感到难过，有人制作了一个几乎与之相同的网页），还有Dave Seal的版本，其中有针对非clzARM的六种指令。的clz 优点是，可以根据输入来产生更快的算法。
除了auselen的良好阅读建议之外，Hacker's Delight这个有点花哨的博客可能会有所帮助，它在图形环境中谈论这些事情。至少我发现了解一些Qt的blitting代码很有用。但是，它在编码人口计数例程中有一些用处。
该carry add单元在分而治之的意义上很有用，从而产生了问题O(ln n)。 clz如果数据具有1或0的游程则更有用。
该黑客的喜悦进入对戴夫圣印的ARM代码更多的背景。