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

In summary: On my compiler of choice (gcc) it is:int __builtin_popcount (unsigned int x) Returns the number of 1-bits in x. #ifdef __x86_64__popcnt64 (x);#elsepopcnt (x);#endifOn my compiler of choice (gcc) it is:int __builtin_popcount (unsigned int x) Returns the number of 1-bits in x. #ifdef __x86_64__popcnt64 (x);
  • #1
burritoloco
83
0
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.
 
Technology news on Phys.org
  • #2


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.
 
  • #3


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.
 
  • #5


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
 

1. What is the purpose of counting '1' bits in binary blocks?

The purpose of counting '1' bits in binary blocks is to determine the number of '1' bits present in a binary number or a block of binary numbers. This can be useful in various applications such as error detection, data compression, and cryptography.

2. How does the fast C++ code for counting '1' bits work?

The fast C++ code for counting '1' bits uses bitwise operators and bit shifting to efficiently count the number of '1' bits in a binary block. It traverses through each bit of the binary number and checks if it is set to '1'. If it is, the count is incremented. This process is repeated until all the bits have been checked, resulting in the total count of '1' bits.

3. What are the advantages of using this fast C++ code for counting '1' bits?

Using this fast C++ code for counting '1' bits has several advantages. It is highly efficient and can process large blocks of binary numbers quickly. It also uses minimal memory and does not require any additional libraries or dependencies, making it easy to implement in various applications.

4. Can this fast C++ code be modified to count '0' bits instead?

Yes, this fast C++ code can be modified to count '0' bits instead. The code can be easily modified to check for '0' bits instead of '1' bits by using the bitwise operator AND (&) instead of OR (|) in the counting process. This will result in the number of '0' bits being counted instead of '1' bits.

5. How accurate is the fast C++ code for counting '1' bits?

The fast C++ code for counting '1' bits is highly accurate. It checks each bit of the binary number individually and increments the count only if the bit is set to '1'. This ensures that all '1' bits are counted accurately without any errors or discrepancies.

Similar threads

  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
13
Views
1K
  • Programming and Computer Science
Replies
23
Views
2K
  • Programming and Computer Science
2
Replies
39
Views
3K
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
1
Views
2K
Replies
17
Views
1K
  • Programming and Computer Science
Replies
6
Views
2K
  • Programming and Computer Science
Replies
3
Views
2K
  • Programming and Computer Science
Replies
6
Views
2K
Back
Top