C/C++ Counting '1' Bits in Binary Blocks - Fast C++ Code

[burritoloco]

Hi,

For example, say we have the binary integer 101010 and I split it into blocks, say (1)(01)(01)(0). The size of the blocks is determined by some function. We want to count the number of '1' bits inside each of these blocks.

I'm interested in a fast C++ code to do this. There are fast codes out there to compute the number of '1' bits in arbitrary integers, and it would be great if the solution to this problem could be obtained by a modification of those codes (which I do not understand), so that it is as fast as it can be. For instance, here's one of those "ugly" fast codes (the one I'm using in my project) which I found in another forum:

int bitcount(int i) {
i = i - ( (i >> 1) & 0x55555555);
i = (i & 0x33333333) + ( (i >> 2) & 0x33333333 );
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0X01010101) >> 24;
}


Many thanks for the help.

 

[chiro]

Hey burritoloco and welcome to the forums.

You can do this with a very simple loop. You loop over all bits in a block and have a counter variable for the number of bits in a block (initialized to zero). Then in the loop you simply do counter += ((Block_Value) >> loop_index) & 1.

What the above does is move the bit of interest to the LSB and then you 'AND' it by 1 to get the value of that bit. Loop_index should start at 0 and go to Num_Block_Bits - 1 inclusive.

 

[rorix_bw]

1) Get hold of a profiler like "gprof" (for gcc) or "valgrind". These time the execution of a program and can break down the time spent in each function, etc.

I consider trying to optimise code without a profiler is unwise. This is "premature optimisation". You think that function is a bottleneck, but how do you know without a profiler?

2) If you compile with optimisations turned on (example: -O2 in gcc) the compiler itself will optimise the code in certain ways. It may completey ignore some branches in your code, or change divisions to bitwise operations, etc,

This is another reason to avoid premature optimisation. The compiler is a "mystery black box" with relation to the source code, so you need a profiler to compare the differences.

3) The code you have given makes use of bit shifting, which is almost certainly hardware accelerated. I would have to check that, but I would be shocked if modern Intel CPUs did not have a hardware circuit specially for this. Again this is further justification for the neccessity of a profiler.

 

[rcgldr]

Some Intel and AMD processors have an instruction called POPCNT, which counts the number of bits in the source and places the count in a destination register. Wiki article:

http://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT

In Visual Studio C / C++ 2010 (including the free express version) popcnt can be accessed using an intrinsic function:

http://msdn.microsoft.com/en-us/library/bb385231.aspx

 

[rorix_bw]

Nice catch.

On my compiler of choice (gcc) it is:

int __builtin_popcount (unsigned int x)
Returns the number of 1-bits in x.

What I would do is autoconf to check it exists and is supported on the hardware. If it does, #define it in. If it doesn't, use my own code.

The function is documented in gcc here: http://gcc.gnu.org/onlinedocs/gcc-4.5.3/gcc/Other-Builtins.html