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

Question

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++;
    }
    return 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. — , Sep 12 '12 at 02: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 02:45
http://softwareengineering.stackexchange.com/questions/304876/explanation-to-why-counting-bits-set-brian-kernighans-way-works — OhadR, Dec 05 '16 at 15:05
so if `N` is the number of bits, then it is `O(N)`, but if `N` is `n`, then it is `O(log N)` — nonopolarity, Feb 12 '17 at 17:18

score 33 · Accepted Answer · answered Sep 12 '12 at 04:10

33

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

answered Sep 12 '12 at 04:10

PengOne

48,188
17
130
149

1

When you say 'n has log(n) bits' do you mean 'significant bits' or just bits. I would assume the number of total bits used to represent an integer would remain constant for a given platform. – Quest Monger Jul 08 '15 at 20:30
3

so I think even if we count the bit one by one, it is still `O(log n)`. Brian Kernighan's algorithm only improve on the average case or best case: if we assume half of the bits are `1`, then the loop is half many times as bit by bit... if the number has just 1 bit that is set, then instead of 32 or 64 times (or whenever that bit is cleared and making `a` become `0`, for example: loop 6 times if it is the 6th bit that is set), then Brian Kernighan's algorithm is just one time through the loop. If only 2 bits are `1`, then Brian Kernighan's algorithm will loop through twice only. – nonopolarity Feb 12 '17 at 17:14
1

@太極者無極而生 more compactly expressed: The naive solution is `theta(log n)` whereas Kernighans is `O(log n)`. – andreee Feb 21 '19 at 23:43

score 8 · Answer 2 · answered Sep 12 '12 at 02:56

8

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)).

answered Sep 12 '12 at 02:56

The_Sympathizer

1,191
9
17

score 5 · Answer 3 · edited Nov 08 '16 at 14:20

This question is really about meaning of N in big O notation, not complexity of algorithm.

N means size of the data. But in case where where "data" is a single number you need to define what you understand as size of data. The value of a number or length of it's representation.

IMO the algorithm is O(N). Because in this problem of counting 1 in binary representation IMO relevant size of data is length of the number's representation, not it's value i.e. the length of the bit stream. And obvious worst case is all 1's taking N iterations.

But if you consider value of N as size of the data, it's representation has log(N) length so you can say it's O(log(N))

PS Also big O notation makes sense only if you generalise algorithm for arbitrarily high Ns. In this code N is limited by int size, so you can say it's O(1) as it will be at most 64 loop iterations (for 64 bit ints)

The code in question uses lowercase n and given that variable the complexity is bounded at O(log n) (lowercase). — Antti Haapala -- Слава Україні, Jan 09 '20 at 23:29
Typically when an algorithm works on an integer, the variable N (upper case) means the integer itself and n (lower case) means the number of bits, i.e. n = log N. — kaya3, Sep 30 '22 at 13:16

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

3 Answers3

Linked