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

Question

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 best 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.)

You meant 1,2,4,8,16,32? That is will the enumerated values be powers of 2? — celavek
– celavek, Commented Apr 2, 2011 at 12:55

Marcelo Cantos · Accepted Answer · 2011-04-02 13:19:48Z

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;

+1 and a minor glitch: i is out of scope when the loop ends :-)

flolo · Accepted Answer · 2011-04-02 13:03:48Z

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,

arul · Accepted Answer · 2011-04-02 12:54:51Z

1

You want to use a binary logarithm:

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

answered Apr 2, 2011 at 12:54

arul

14.1k1 gold badge60 silver badges78 bronze badges

Comments

celavek · Accepted Answer · 2011-04-02 12:59:09Z

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

thkala · Accepted Answer · 2011-04-02 13:09:34Z

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.

Collectives™ on Stack Overflow

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

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Related