Bit Operation Counting

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

Quote by noblerare

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:

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.

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 realised logical operators aren't really allowed

i.e.

a = b < 3

probably implies a conditional

Similar discussions for: Bit Operation Counting
Thread	Forum	Replies
closed operation	General Math	3
Simple Set Operation	Calculus & Beyond Homework	1
Matrix operation	Calculus & Beyond Homework	5
Binary operation	Set Theory, Logic, Probability, Statistics	3
Set operation problem	Set Theory, Logic, Probability, Statistics	5

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

technoweasel	Bit Operation Counting 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 Recognitions: Gold Member Science Advisor Staff Emeritus	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.

rcgldr Recognitions: Homework Help	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.