有人能解释一下为什么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)。
while(n!=0)
。否则负数将无法正确计数。 - Nathan Andrew MullenaxN
是位数,则为O(N)
,但如果N
是n
,则为O(log N)
。 - nonopolarity