最快的方式来计数寄存器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:

写快速code，将计算一个32位寄存器1的数。

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

现在我在学习臂组件的过程。所以很自然，我再次重新审视这个问题，刚才通过研究ISA想出这个code。

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.

为您手臂的专家在那里，这是正确的？是否有一个更快的方法来做到这一点？作为一个初学者，我自然认为这是不完整的。在XXAND指令感觉多余，但有没有其他办法移入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包含的比特数在末尾而R 2是与我们要计数位寄存器。 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)

推荐答案

您可以使用precomputed查找表，减少迭代次数为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.

有关详细信息请参见这个维基百科文章。

这篇关于最快的方式来计数寄存器1的个数，ARM汇编的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！