计算手臂组件中的位数

Question

我找到了以下代码，用于在 Arm 汇编中以最少的指令数计算 4 字节整数中的位：

  ;R0 - value
  ;R1 = number of ones
  ;Uses R0-R1
  ;81 cycles worst case, 4 cycles best case, exit when r1=0

mov    r1,r0,lsr #31
loop   movs     r0,r0,lsl #2    
       adc  r1,r1,r0,lsr #31    
       bne  loop
       mov  pc,r14

你能解释一下这里的算法是什么吗？虽然我知道所有指令的作用，但我还是看不懂。

Answer 1

       mov    r1,r0,lsr #31        @ start with r1 = the high bit of r0 (right shift by 31 bits)
loop   movs     r0,r0,lsl #2       @ left shift r0 by 2, and set flags on the result
       adc  r1,r1,r0,lsr #31
       bne  loop                   @ loop if r0 is non-zero (testing flags set by movs)

加进位是一个巧妙的技巧：r0 >> 31 是高位，进位标志是被 movs r0,r0,lsl #2 移出的位（我假设 ARM 这样做像 x86 的方式，否则算法没有意义。）

因此它每次迭代将 2 位添加到 popcnt 总数：高位和移出的最后一位。

这是不是最快的 popcnt 方法。

上一个问题：Fastest way to count number of 1s in a register, ARM assembly 解决了这个问题，其中一个答案使用 vcnt.8 d0, d0 然后是四个 8 位计数的水平和。 None 那里的答案提到了这个一次两位循环。

即使没有 LUT（例如 8 位 LUT 来查找每个字节的计数）或专用的 popcnt 指令，也有 bithacks，like this one from Sean Anderson's collection:

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

恒定时间没有分支，但确实需要几个 32 位常量（每条指令需要两条指令才能进入 ARM 上的 regs）

计算手臂组件中的位数

Counting bits in arm assembly

assembly

arm

bit-manipulation

bits