10

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

给定一个 32 位整数i，计算第n个最低有效位的位置。n和结果都应该是 0-indexed。

例如，给定数字i = 11010110101 2和n = 4，所需的数字是 7，因为第四个设置位位于位置 7：110 1 0110101。

使用pdepx86 的 BMI2 指令集扩展中的指令和常用的__builtin_ctz()内在函数，可以轻松计算：

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

但是，许多计算机没有该pdep指令（并且在有该指令的 AMD CPU 上速度很慢），这使得这种方法不可移植。您也可以计算这样的位位置，而不是pdep这样：

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

return (__builtin_ctz(j));

但是，这很慢。

我的目标是至少提供__builtin_popcount()和__builtin_ctz(). 我怎样才能更快地找到这样的位位置？

4

0 回答 0