# Bit Operation Counting

1. Jan 23, 2010

### 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

2. Jan 25, 2010

### silverfrost

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

3. Jan 25, 2010

### CRGreathouse

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?

4. Jan 29, 2010

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

5. Jan 29, 2010

### Hurkyl

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.

6. Jan 30, 2010

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

7. Jan 30, 2010

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

8. Jan 30, 2010

### Hurkyl

Staff Emeritus
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 (Text):

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 (Text):

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.

9. Feb 2, 2010

### 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