Efficiently Count Bits in 32-bit Integers using Bit Operations

[noblerare]

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

 

[silverfrost]

no loops or conditionals sounds unlikely. Not much can be done without 'if' and 'goto'.

 

[CRGreathouse]

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?

 

[technoweasel]

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.

 

[Hurkyl]

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.

 

[silverfrost]

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.

 

[rcgldr]

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.

 

[Hurkyl]

Bit twiddling might be faster than the random access lookup into 2 GB too.


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:

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:

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.

 

[silverfrost]

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