高效查找第n位索引

Question

给定一个位掩码，我想找到第 n 个 1 位的索引。例如，使用掩码 00001001 和数字 1 将返回索引 3。使用数字 0 的相同掩码将返回 0。我需要尽可能高效地执行此操作。我想出的最好的办法是：

    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
    }

有什么办法可以提高效率吗？我不喜欢

while

和

if

语句，这主要导致效率低下。最好立即检索它，但不确定这是否可能，或者是否有任何可以进一步利用的内置 GCC 函数。

非常感谢任何帮助，谢谢！

我已经尝试了上面的

while

循环，但似乎还不够。

Answer 1

您可以使用这个更简单的版本：

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;
}

或者为了尽量减少跳跃，这个展开的版本：

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;
}

如果

mask

只有8位，你可以使用查找表。