Find nth bit index efficiently

Question

Given a bit mask, I'd like to find the index of the nth 1 bit. For example with mask 00001001 and number 1 would return index 3. Same mask with number 0 would return 0. I need to do this as efficiently as possible. The best I came up with is this:

    while (mask) {
        int i = __builtin_ctz(mask);  // Find the index of the lowest set bit
        if (count == idx_num) {
            return i;
        }
        count++;
        mask &= (mask - 1);  // Clear the lowest set bit
    }

Is there any way to make this more efficient? I do not like the while and if-statement, which mainly cause the inefficiency. It'd be best to have it retrieved immediately but not sure if that's possible or if there are any builtin GCC functions that could be further capitalized on.

Would appreciate any help, thank you!

I've tried the above while loop but it doesn't seem to suffice.

Answer 1

You could use this simpler version:

int get_nth_bit_index(unsigned mask, unsigned idx_num) {
    while (idx_num--) {
        mask &= (mask - 1);  // Clear the lowest set bit
    }
    return mask ? __builtin_ctz(mask) : 0;
}

Or to minimize jumps, this unrolled version:

int get_nth_bit_index(unsigned mask, unsigned idx_num) {
    switch (idx_num) {
      default: while (idx_num --> 9) mask &= mask - 1;
              mask &= mask - 1;
      case 8: mask &= mask - 1;
      case 7: mask &= mask - 1;
      case 6: mask &= mask - 1;
      case 5: mask &= mask - 1;
      case 4: mask &= mask - 1;
      case 3: mask &= mask - 1;
      case 2: mask &= mask - 1;
      case 1: mask &= mask - 1;
      case 0: break;
    }
    return mask ? __builtin_ctz(mask) : 0;
}

If mask is only 8 bits, you could use a lookup table, and with some effort, this lookup table can be used for larger mask types.

Here is a branchless version for 32-bit values using 2304 bytes of lookup tables. These tables must be initialized separately either at program startup time or at build time using a script:

#include <stdint.h>

enum { TABLE_BITS = 8, TABLE_LEN = 256, TABLE_MASK = 255 };

unsigned char bit_count[TABLE_LEN];
unsigned char nth_bit[TABLE_BITS][TABLE_LEN];

void initialize_nth_bit_tables(void) {
    for (unsigned i = 0; i < TABLE_LEN; i++) {
        unsigned count = 0;
        for (unsigned n = i; n; count++)
            n &= n - 1;
        bit_count[i] = count;
    }
    for (unsigned i = 0; i < TABLE_BITS; i++) {
        for (unsigned j = 0; j < TABLE_LEN; j++) {
            unsigned mask = j;
            for (unsigned idx = i; idx; idx--) {
                mask &= mask - 1;
            }
            nth_bit[i][j] = mask ? __builtin_ctz(mask) : 0;
        }
    }
}

unsigned get_nth_bit_index32(uint32_t mask, unsigned idx) {
    unsigned pos = 0, test;
    test = idx >= bit_count[m & TABLE_MASK];
    idx -= bit_count[mask & TABLE_MASK] * test;
    pos += TABLE_BITS * test;
    mask >>= TABLE_BITS * test;
    test = idx >= bit_count[m & TABLE_MASK];
    idx -= bit_count[mask & TABLE_MASK] * test;
    pos += TABLE_BITS * test;
    mask >>= TABLE_BITS * test;
    test = idx >= bit_count[m & TABLE_MASK];
    idx -= bit_count[mask & TABLE_MASK] * test;
    pos += TABLE_BITS * test;
    mask >>= TABLE_BITS * test;
    test = idx < TABLE_BITS;
    return pos + nth_bit[idx * test][mask & TABLE_MASK];
}