Efficent way of mapping bit mask values (1, 2, 4, 8, etc.) into a vector index (1,2,3,4, etc.)

I have an enmeration with a set of values which can be bitwise or'd together:

enum EventType_e
{
    EventType_PING  = 1,
    EventType_PANG  = 2,
    EventType_PONG  = 4,
    EventType_PUNG  = 8
};

I expect this enumeration to grow to contain at most 15-20 items. On receiving one of these enumerated values I would like to be able to map it to a vector, but instead of having a sparse array I'd like to collapse the values down. What is the be开发者_Go百科st way of mapping 1,2,4,8,16,32 to 1,2,3,4,5,6 (i.e. finding 'x' in 2^x=1, 2^x=2, 2^x=4, 2^x=8, etc.)

Most modern CPU architectures have opcodes to discover the most or least significant non-zero bit in a number (e.g., BSF and BSR on x86). These are also available as intrinsics on some compilers, such as _BitScanForward and _BitScanReverse on Microsoft and Intel compilers.

The above bit-scan is hands-down the fastest solution. For a more portable solution, shift right until the bit drops off the end:

int i;
for (i = 0; n >>= 1; ++i) { }

Note that this returns 0, 1, 2, 3, which is more appropriate for vector indexing than 1, 2, 3, 4.

A more complex but faster portable solution is a binary chop:

// Logically, we initialise i to 0, and add n - 1 at the end. Initialising
// to -1 avoids the subtraction. This is splitting hairs somewhat, and who
// knows — initialising to -1 instead of zero might be slow!
int i = -1;
if (n >> 16) { n >>= 16; i += 16; }
if (n >>  8) { n >>=  8; i +=  8; }
if (n >>  4) { n >>=  4; i +=  4; }
if (n >>  2) { n >>=  2; i +=  2; }
i += n;

The function for "finding x" is called logarithm. In this case log2. There is no standard C log2 function for ints, and computing is a small loop. Depending on your architecture your cpu has maybe an asm instruction to get the highest bit, which does the same.

Better solution in my eyes is to it the other way around.

Define something like

#define PING 1
#define PANG 2
#define PONG 3
#define PUNG 4

(You could also use enum here).

And then make in your event enum something like

EventType_PING 1 << PING,
EventType_PANG 1 << PANG,
EventType_PONG 1 << PONG,
EventType_PUNG 1 << PUNG,

You want to use a binary logarithm:

#include <cmath>
double power = log2n(number);

If the enumerated values will be powers of 2 then I subscribe to the answers that already suggest log2 (they beat me to it) but "advising" you to use some "fancy" Bit Twiddling Hacks (check the sections find log base 2 of an integer).

What you are essentially asking for is: "Given a power of 2 stored in an integer X, what is the most efficient way to find the exponent E?"

The simple approach would be to search for that significant non-zero bit:

int E = 0;
while (X >>= 1)
    E++;

Note that this will output E = 0 for X = 1 - you may want to initialise E to 1 to have E = 1 for X = 1.