Efficiently Count Bits in 32-bit Integers using Bit Operations

  • Thread starter Thread starter noblerare
  • Start date Start date
  • Tags Tags
    Bit Counting
AI Thread Summary
The discussion centers on finding a method to count the number of bits to the left and right of a '1' in a 32-bit integer using only bit operations, without loops or conditionals. Participants express skepticism about achieving this without some form of conditional logic, emphasizing the challenge of performing such operations efficiently. Suggestions include using bit manipulation techniques and leveraging assembly language instructions available on newer processors. There is mention of using native operations like popcount, leadz, and trailz for better performance. A detailed example of a popcount function is provided, demonstrating how to count the number of '1's in a 32-bit integer using bitwise operations. The conversation highlights the complexity of the task and the potential for using lookup tables to optimize performance, while also noting the limitations imposed by the requirement to avoid logical operators that imply conditionals.
noblerare
Messages
49
Reaction score
0
Hi all,

I am wondering is there a way to count the number of bits to the left or right of a given 1 in a 32-bit integer?

For example, if I give the function the number 32 = 0b100000, there are 5 bits to the right of the 1 and hence, 26 bits to the left of the 1.

The catch is, is there a way to do this by simply using bit operations? i.e. no loops or conditionals? Bit operations include: & ^ | << >> ! and ~

Thanks
 
Technology news on Phys.org
no loops or conditionals sounds unlikely. Not much can be done without 'if' and 'goto'.
 
noblerare said:
The catch is, is there a way to do this by simply using bit operations? i.e. no loops or conditionals? Bit operations include: & ^ | << >> ! and ~

Yes, as can all such functions. The question is whether this can be done efficiently.

I'm not entirely sure I understand your function, though. It looks like the first part is counting trailing zeros, and the second part is 31 minus the first part. Is that right?
 
I have been looking into bitboards in chess programming a bit and found that some newer processors have assembly language instructions that might solve your problem, but I have no specifics.
 
There are lots of tricks you can use with bit twiddling -- but your probably much better off learning how to invoke native operations rather than trying to roll your own (and you will probably get better performance too) -- functions like like popcnt, leadz and trailz.
 
I would be curious to see the function -- given there are no loops or conditionals. Clearly that means no implied loops or conditionals (i.e. no function calls, intrinsics or conditional operators). I have heard it said you can do anything with a couple of logic operators but never seen a real example.
 
You could split the number into two 16 bit values and use each value to index into one of two tables with 65536 entries. If you have the ram, a single look up into a table with 4gb entries would work, although it would take a bit to initialize the table.
 
Bit twiddling might be faster than the random access lookup into 2 GB too. :wink:


If you really want a popcount function and your compiler doesn't offer you a builtin function to do it, you can do something like this:

Code:
uint32_t evens = x & 0x55555555;
uint32_t odds = x & 0xaaaaaaaa;
uint32_t two_long_counts = evens + (odds >> 1);
evens = two_long_counts & 0x33333333;
odds = two_long_counts & 0xcccccccc;
uint32_t four_long_counts = evens + (odds >> 2);
uint32_t eight_long_counts = four_long_counts + (four_long_counts) >> 4;
evens = eight_long_counts & 0x000f000f;
odds = eight_long_counts & 0x0f000f00;
uint32_t sixteen_long_counts = evens + (odds >> 8);
return (sixteen_long_counts + (sixteen_long_counts >> 16)) & 0x3f;

This computes the number of 1's in a 32-bit word. I think there are faster ways to do it too. This can be used to compute trailz:

Code:
uint32_t find_lowest_one = x & -x;
uint32_t make_all_smaller_bits_one = find_lowest_one - 1;
return popcount(make_all_smaller_bits_one);

You probably get better performance out of writing a divide-and-conquer version directly. A small lookup table can be useful to accelerate things -- also note you can do things like pack a 16-long lookup table of 2-bit entries into a single 32-bit word.
 
Nice answer Hurkyl but not what the questioner wants - he wants the number of zeros to the right of the first one bit (and hence the number on the other side).

I thought I had figure it out but then realized logical operators aren't really allowed

i.e.

a = b < 3

probably implies a conditional
 
Back
Top