Convert power of 2 bitmask into corresponding index

Question

I've been looking around for an answer to this, but haven't found any decent solutions. I'm trying to convert a single-enabled-bit (32-bit mask) into its corresponding index location. The mask has only one bit enabled, from bit 0 to bit 31.

So here are the conversions I'm looking for: 1=1, 2=2, 4=3, 8=4, 16=5, 32=6, etc..

I'm not against making a lookup table, if the table isn't both terribly large and mostly empty. Is there any clever math out there to accomplish this in one step (without looping through the bits)?

EDIT: I could not find a satisfactory answer in the link provided. But after goofing around with some numbers, I did stumble onto a magic value that separates power of two values perfectly for 32 bit masks. That value is 37. If you modulate any 32-bit power of 2 value by 37, it will convert that power of two value into an index between 1 - 36. This means we can create a tiny lookup table of 37 values, with only a few entries wasted. Here is the fill rate of that table: |0|1|1|1|1|1|1|0|1|1|1|1|1|1|0|1|1|1|1|0|1|1|1|1|1|1|1|1|0|1|1|1|1|1|1|1|1|

I will mess around a little more to see if such a thing is possible with 64 bit values.

I don't understand why this forum is so quick to close topics. It makes it impossible to have any type of discussion about something that has been discussed before.

This question should have tons of dupes. Please do some research. — Evg, Mar 19 '22 at 14:50
“I’m not against a lookup table if it isn’t very large” the size of such a table should be obvious. But only you can answer if you consider that too large or not. — Taekahn, Mar 19 '22 at 15:12
Your best bet to do what you want to do is probably to count leading or trailing 0 bits, since only one is set. https://stackoverflow.com/questions/31374628/fast-way-of-finding-most-and-least-significant-bit-set-in-a-64-bit-integer/31377558#31377558 — Taekahn, Mar 19 '22 at 15:18
If you are looking for C++ specific answer, C++20 provided [`countr_zero`](https://en.cppreference.com/w/cpp/numeric/countr_zero) and [`bit_width`](https://en.cppreference.com/w/cpp/numeric/bit_width) — Ranoiaetep, Mar 19 '22 at 17:45
FYI, you can just modulate the power of two by 37 and put the result into a lookup table[37]. — Robert, Mar 19 '22 at 18:08
Thanks @Ranoiaetep, I had no idea those methods existed. Any idea how they work internally? — Robert, Mar 19 '22 at 18:16

score 2 · Answer 1 · answered Mar 19 '22 at 15:17

Here is a solution inspired from Bit Twiddling Hacks:

first decrement the value to set all bits below the index to 1
then count the number of bit in the resulting value
add 1 to get the expected result

int bit_index(uint32_t v) {
    v -= 1;
    v = v - ((v >> 1) & 0x55555555);                // reuse input as temporary
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
    return 1 + (((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24); // count
}

score 0 · Answer 2 · answered Mar 19 '22 at 15:05

Simply shift the bits to the right until all are zero:

#include <stdio.h>

int main(void)
{
    int n, pos, x;

    n = scanf("%d", &x);
    if (n == 1) {
        pos = 0;
        while (x != 0) {
            x >>= 1;
            pos++;
        }
        printf("%d\n", pos);
    }
    return 0;
}

Convert power of 2 bitmask into corresponding index

2 Answers2