## Bit Operation Counting

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
 PhysOrg.com science news on PhysOrg.com >> Leading 3-D printer firms to merge in $403M deal (Update)>> LA to give every student an iPad;$30M order>> CIA faulted for choosing Amazon over IBM on cloud contract
 no loops or conditionals sounds unlikely. Not much can be done without 'if' and 'goto'.

Recognitions:
Homework Help
Science Advisor
 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?

## 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.
 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.
 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.
 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.
 Recognitions: Gold Member Science Advisor 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: 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 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 General Math 3 Calculus & Beyond Homework 1 Calculus & Beyond Homework 5 Set Theory, Logic, Probability, Statistics 3 Set Theory, Logic, Probability, Statistics 5