如何有效地找到第n个设置位？

Question

对于与此问题相关的代码,我需要尽快计算以下内容:

给定32位整数i,计算第n个最低有效位集的位置.无论ñ和结果应该是0索引.

例如,给定数字i = 11010110101 ₂且n = 4,所需数字为7,因为第四设置位在位置7:110 1 0110101.

使用pdep来自x86的BMI2指令集扩展的指令和常用的__builtin_ctz()内部函数,可以很容易地计算出来:

j = _pdep_u32(1 << n, i);
return (__builtin_ctz(j));

但是,许多计算机没有pdep指令,这种方法略显不切实际.你也可以不用pdep这样计算这样的位位置:

j = i;
for (k = 0; k < n; k++)
    j &= j - 1;

return (__builtin_ctz(j));

但是,这很慢.

我瞄准的是至少提供电脑__builtin_popcount()和__builtin_ctz().如何更快地找到这样的位位置？