# Bits counting algorithm (Brian Kernighan) in an integer time complexity

Can someone explains why Brian Kernighan's algorithm takes O(log N) to count set bits (1s) in an integer. A simple implementation of this algorithm is below (in JAVA)

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

I understand how it works by clearing the rightmost set bit one by one until it becomes 0, but I just don't know how we get O(log N).

-
n is represented by log(n) bits. (Conversely, k bits can represent numbers as high as 2^k.) Checking each bit takes constant time, so we end up with log(n) time. –  bdares Sep 12 '12 at 2:35
In Java, it should probably be `while( n!=0 )`. Otherwise negative numbers won't be counted properly. –  Nathan Andrew Mullenax Sep 12 '12 at 2:45
I see..just corrected it –  user1389813 Sep 12 '12 at 2:50

This algorithm goes through as many iterations as there are set bits. So if we have a 32-bit word with only the high bit set, then it will only go once through the loop. In the worst case, it will pass once per bit. An integer `n` has `log(n)` bits, hence the worst case is `O(log(n))`. Here's your code annotated at the important bits (pun intended):

``````  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++;
}
}
``````
-

There are floor(lg(N)) + 1 significant bits in N -- that's a base-2 logarithm. The number of 1 bits in n is at most this. So the time will have asymptotic upper bound O(lg(N)) = O(log(N)).

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}