整数时间复杂度的比特计数算法(Brian Kernighan)
有人能解释为什么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 )。
回答 3
Stack Overflow用户
发布于 2012-09-12 04:10:23
这个算法会经历与设置位一样多的迭代。因此，如果我们有一个只设置了高位的32位字，那么它将只经过一次循环。在最坏的情况下，它将通过每位一次。整数n具有log(n)位，因此最坏的情况是O(log(n))。下面是你的代码中重要的部分注释(双关语)：
int count_set_bits(int n){
int count = 0; // count accumulates the total bits set
while(n != 0){
n &= (n-1); // clear the least significant bit set
count++;
}
}Stack Overflow用户
发布于 2012-09-12 02:56:28
在N中有floor(lg(N)) +1个有效位--这是一个以2为底的对数。N中的1比特的数目至多为this。因此，时间将具有渐近上界O(lg(N)) = O(log(N))。
Stack Overflow用户
发布于 2016-11-08 13:45:17
这个问题实际上是关于N在大O符号中的意义，而不是算法的复杂性。
N表示数据的大小。但在" data“是单个数字的情况下，您需要定义您所理解的数据大小。一个数字的值或其表示的长度。
IMO算法为O(N)。因为在二进制表示中计数1的问题中，数据的相关大小是数字表示的长度，而不是它的值，即比特流的长度。显然最坏的情况是所有的1都需要N次迭代。
但是如果你考虑N的值作为数据的大小，它的表示具有log(N)长度，所以你可以说它是O(log(N))
PS也是大O符号，只有当你将算法推广到任意高的Ns时才有意义。在这段代码中，N受到int大小的限制，所以您可以说它是O(1)，因为它最多64次循环迭代(对于64位int)
https://stackoverflow.com/questions/12380478
复制
腾讯云开发者
