计算寄存器中 1 数量的最快方法，ARM 程序集 [英] Fastest way to count number of 1s in a register, ARM assembly

问题描述

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

So I had an interview question before regarding bit manipulation. The company is a well known GPU company. I had very little background in assembly language (weird despite being a phd student in computer architecture) and as this narrative would indicate, I botched it. The question was a simple:

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

"Write a fast code that will count the number of 1's in a 32-bit register."

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

Now I am in the process of studying arm assembly. So naturally I revisited this problem again and have come up with this code just by studying the ISA.

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

For you arm experts out there, is this correct? Is there a faster way to do this? Being a beginner, I naturally think this is incomplete. The AND instruction in "xx" feels redundant but there is no other way to shift a register in ARM isa...

R1 将包含末尾的位数，而 R2 是包含我们要计数的位数的寄存器.r6 只是一个虚拟寄存器.注释包含在 ()

R1 will contain the number of bits at the end while R2 is the register with bits we want to count. r6 is just a dummy register. Comments are enclosed in ()

    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)

推荐答案

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

You could use a precomputed look up table and reduce the number of iterations to 2 or 4.

您也可以使用对数方法.

You could also use the logarithmic approach.

有关详细信息，请参阅这篇维基百科文章.

For more info see this Wikipedia article.

这篇关于计算寄存器中 1 数量的最快方法，ARM 程序集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！