Efficient counting 1s in a binary sequence

[kinley]

Hi,

I would like to know how to count the number of 1s in a binary sequence such as 0110111000110 of length N very efficiently.

I can use a for loop to iterate from 0 to N-1 and count 1s but in this way the complexity would be O(N).

Please suggest me if there is something even more efficient?

I am looking at an N which is around a million bits.

Thank you.

[giblit]

You could use a bitset and then use the count member functions.

http://www.cplusplus.com/reference/bitset/bitset/count/

Also how are you getting the binary number? You could simply set a counter and increment by one when ever you read in a 1.

*edit

Another method would be to shift it right and when ever the right bit is a 1 increment the count by one. But this is probably just as bad as a for loop.

int count = 0;
while( number ) //while any bits are set not sure how you are getting the value
{
    count += number & 1;
    number >> 1;
}

There is also kernigans method which should be a lot faster than o(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <iostream> //this test will output the result and return number of iterations required int method1( int n ); //simple - bitwise - O(bits) == O(n) int method2( int n ); //Kernigan's method - O(bitsset) < O(n) not sure exact ratio int main() { int n = 3526; //0110111000110 - 7 bits set int it1 = method1(n), it2 = method2(n); //iterations required std::cout << "Iterations required method1: " << it1 << std::endl; std::cout << "Iterations required method2: " << it2 << std::endl; return 0; } int method1( int n ) { int count = 0 , i; for( i = 0; n; ++i ) { count += n & 1; n >>= 1; } std::cout << "Bits set: " << count << std::endl; return( i); } int method2( int n ) { int i; for( i = 0; n; ++i ) { n &= n - 1; } std::cout << "Bits set: " << i << std::endl; return( i ); }

Bits set: 7 Bits set: 7 Iterations required method1: 12 Iterations required method2: 7

http://ideone.com/Zyzsis

[Duthomhas]

If you are looking for efficiency, you should head over to the Bit Twiddling Hacks page.
http://graphics.stanford.edu/~seander/bithacks.html
(Scroll down to "counting bits set".)

Hope this helps.

[JLBorges]

Compilers typically provide intrinsics for efficiently counting bits; most modern processors have a population count machine instruction.

The safe, portable, option is to use std::bitset<>::count(); the machine code generated would typically be the most efficient code available on the target hardware architecture.

/* g++ -std=c++11 -Wall -Wextra -pedantic-errors -O3 -march=corei7 
       -fomit-frame-pointer -fexpensive-optimizations -c -S test.cc */
/* .ident	"GCC: (GNU) 4.9.0 20131201 (experimental)" */

// Note: corei7 has SSE4.2 (popcnt instruction)

#include <limits>
#include <bitset>

#ifdef __GNUG__
int foo_builtin_popcnt( unsigned int a )
{
    // http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
    return __builtin_popcount(a) ;

    /*
        __Z18foo_builtin_popcntj:
            popcntl	4(%esp), %eax
            ret
    */

}
#endif // __GNUG__


#ifdef _MSC_VER
int foo_builtin_popcnt( unsigned int a )
{
    // http://msdn.microsoft.com/en-us/library/bb385231(v=vs.100).aspx
    return __popcount(a) ;
}
#endif // _MSC_VER


int foo_bitset( unsigned int a )
{
    return std::bitset<std::numeric_limits<unsigned int>::digits>(a).count() ;

    /*
        __Z10foo_bitsetj:
            popcntl	4(%esp), %eax
            ret
    */
}

[kinley]

Thank you.

All the answers are highly appreciated.

The Bit Twiddling Hacks page mentioned above is pretty resourceful.