相关疑难解决方法(0)

有人可以解释为什么Brian Kernighan的算法需要O(log N)来计算整数中的设置位(1).这个算法的简单实现如下(在JAVA中)

int count_set_bits(int n){
    int count = 0;
    while(n != 0){
        n &= (n-1);
        count++;
    }
    return count;
}

我通过逐个清除最右边的设置位直到它变为0来理解它是如何工作的,但我只是不知道我们如何获得O(log N).

关于位操作,我之前有一个面试问题.该公司是一家知名的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)

所以我必须在C中找到unsigned char变量的设置位(在1上)？

类似的问题是如何计算32位整数中的设置位数？但它使用的算法不易适应8位无符号字符(或不明显).