查找位范围内第一个设置位的位置
Finding the position of the first set bit within a range of bits
在我的代码中，我发现处理器大部分时间都花在下面显示的函数上。循环的objective就是要找出满足循环内条件的val1值。变量 Val1 和 a 的类型为 long long int（64 位）。而且，它们是在函数内部声明的局部非静态变量。
long long int findval(long long int x)
{
long long int Val1,a=x;
for (Val1 = 63; Val1 > 22; Val1--)
{
if (((a >> Val1) & 1) == 1)
break;
}
return Val1;
}
还有其他simple/optimized方法可以找出 Val1 值吗？
首先，请记住，仅仅因为您发现处理器大部分时间都花在那个 function 片段上，并不意味着有片段的问题。也许您应该尝试找出为什么您的代码如此频繁地调用该代码段。
其次，既然你是来这里寻求帮助的，你不妨向我们展示你所拥有的一切，而不是你所拥有的一部分你认为应该足以让我们找出问题所在的子集。最重要的是，你真的应该向我们展示你的变量是如何声明的以及它们的确切位置声明。它们是局部函数吗？他们是static吗？会不会是你声明了一些东西volatile？没有什么是无关紧要的，一切都很重要。
无论如何，如果我们假设代码段可以优化，那么我会说以下内容：
您的 Val1 应该 而不是 是 long long int，因为它的值仅在23 和 63。因此，它应该是 int。
（如果由于某些原因 Val1 必须 计算为 long long int，然后尝试转换它到循环之前类型为 int 的另一个变量，并在循环中使用该变量。）
如果您尝试这样做，那么编译器可能能够弄清楚您正在尝试做的是找到位范围内的第一个非零位，并用一条机器指令替换整个循环.
警告：我的回答写错了（右边第一位），抱歉。无论如何，这些方法可以很容易地适应 MSb。
您可以通过查找来简化流程 table。您预先计算了从 0 到 2^k-1 的所有数字最右边位的索引。您将一次处理 k 位的切片中的数字，并尝试从右到左切片，直到切片不为零。
一个有趣的选择是将 long long 映射到一个八字节的数组；字节对应于 256 个条目的 lookup-table。这样，您就可以直接按字节寻址。
也可以通过 shorts 进行处理，但代价是 65536 (64K) 个条目的 LUT。最佳可能介于两者之间。有缓存效果。
另一种有用的方法是二分法：屏蔽掉 32 位高位（或加载低位 int）并测试零。然后用非零部分屏蔽掉高 16 位，依此类推。最后，使用 LUT 技巧。只需 3 步，您就可以从 64 人减少到 8 人。
如果比特索引的分布是均匀的，这是合适的。如果偏向于小值，顺序搜索还是可以的。
如果你可以使用 GCC intrisic 那么你可以尝试这样的事情
请注意，这里假定 x 不为 0，因为当 x 为 0
时 __builtin_clzll() 的结果未定义
#include <limits.h>
long long int findval(long long int x)
{
// Get size of long long in bits
size_t llsize = sizeof(long long) * CHAR_BIT;
// Subtract count of leading zeros from size of long long
return llsize - __builtin_clzll(x);
}
出于某种原因，我认为这在某些时候被标记为 x86 and/or x86-64。我的 GNU C 答案适用于任何 ISA，但我专注于 MSVC 的 x86 特定内在函数，以及它如何使用 GCC/clang 为 x86 编译。不幸的是，没有一种完全可移植的方法可以有效地执行此操作，因此 绝对值得做一些 #ifdef 以利用 HW 对您关心的目标上的此操作的支持。
您似乎想要 max(22, 63 - clz(x))，其中 clz 是一些计数前导零函数。例如在 GNU C 中，__builtin_clzll()。 63-clz(x) 是 MSB 的位置，当 long long = int64_t 就像在 x86 上一样。
您的 Val1 > 22 循环条件在 Val1 = 22 处变为假，因此如果到那时没有找到设置位，这就是非 break 退出循环的方法。
__builtin_clzll 在其输入为零 () 时具有未定义的行为。 我们可以通过在 运行 位扫描之前在输入中设置该位来处理这个 和 22 的下限。
#include <limits.h>
inline
int MSB_position_clamped (long long x)
{
int maxpos = CHAR_BIT * sizeof(x) - 1;
x |= 1LL << 22; // avoid x==0 UB and make clz at least 22
return maxpos - __builtin_clzll(x);
}
对于 MSVC，您需要 _BitScanReverse64（在 AMD 上速度较慢）或 63 - _mm_lzcnt_u64（需要 BMI1）。 _mm 内部版本可用于所有 x86-64 编译器。
（正如 Mike 指出的那样，移位计数只需要 int。更宽的移位计数没有帮助，尤其是在为 long long 需要 2 个寄存器的 32 位机器编译时）。
这对 x86-64 编译效率很高，尤其是使用 clang (Godbolt)。我们还希望它能够有效地内联到这 2 条指令。
# clang 9.0 -O3 for x86-64 System V
MSB_position_clamped:
or rdi, 4194304
bsr rax, rdi
ret
(x86 传统位扫描指令直接找到位位置，如您所愿。BMI1 lzcnt 在 AMD 上速度更快，但实际上计算前导零，因此您需要从类型宽度中减去它. 即使 GCC 使用 BSR，它也无法将 63 - clz 优化回 BSR；它翻转了两次。）
请注意，即使只有 重要 位较低，负 2 的补码整数也会设置其 MSB。你确定你想要一个签名类型吗？
如果是这样，您确定不需要 GNU C __builtin_clrsbll？ （Returns x 中的前导冗余符号位数，即最高有效位之后与其相同的位数）没有单个 x86 指令，但我假设它通过 ~x 上的位扫描有效地完成它并以某种方式组合。
此外，如果您的原始代码旨在完全移植到所有 ISO C 实现，我不确定是否保证符号位移动到较低的位位置。我不希望它在 sign/magnitude C 实现中用于带符号的右移。 （ISO C 将有符号整数类型的右移是逻辑运算还是算术运算留给实现；理智/高质量的实现选择算术。使用 2 的补码整数，您的代码将以任何一种方式工作；您不关心它是否向零移动或符号位的副本。）
许多 CPU（不仅仅是 x86）有 bit-scan instructions 在一条硬件指令中执行此操作，但据我所知无法编写 可移植 C 将编译成这样的指令。 ISO C 没有费心去添加可以使用此类指令（当它们存在时）的标准函数。 所以唯一好的选择是特定于编译器的扩展。（一些编译器确实识别 popcount 循环，但是当你的循环停止在 22 而不是 0 时，它不太可能适合 CLZ 的模式如果任何编译器都在寻找它，就可以识别它。）有些语言在这方面比 C 更好，特别是 Rust 具有设计非常好的包括位扫描的整数原语。
GNU C __builtin_clzll() 在有硬件指令的 ISA 上编译为硬件指令，否则回退到调用库函数。 （IDK 回退的效率如何；它可能一次使用一个字节或半字节 LUT 而不是简单的移位。）
在 32 位 x86 上，__builtin_clzll 在低半部分和高半部分使用 bsr 并将结果与 cmov 或分支组合。 _BitScanReverse64 和 _mm_lzcnt_u64 等纯内在函数在 32 位模式下不可用，因此如果您使用内在函数而不是 GNU C "portable" 内置函数，则必须自己做。
32 位代码不如 64 位代码好，但它仍然是非循环的。 （而且你的循环变得非常低效；GCC 不会 "think of" 在低 32 位之前在单独的循环中尝试高 32 位，所以它必须 shrd / sar 然后 cmov 基于移位计数超过 32 的位测试。(Godbolt)。Clang 仍然完全展开，并且确实利用了只测试相关数字的一半。
由于您标记了此 SIMD，x86 AVX512CD 实际上在一个向量寄存器中的 2、4 或 8x int64_t 元素上有一条 lzcnt 指令：vplzcntq.内在是 __m512i _mm512_lzcnt_epi64(__m512i a);.
所有支持 AVX512 的真实 CPU 都有 AVX512CD。
在 Skylake-X 和 Ice Lake 上，它解码为具有 4 个周期延迟、0.5 个时钟吞吐量的单个 uop。 (https://uops.info/)。 （看起来它与 FMA/mul/add FP 指令在相同的端口上运行，可能使用相同的硬件来规范化浮点尾数，该操作也需要找到 MSB。）
因此，希望 GCC 和 clang 可以自动向量化使用 __builtin_clzll 的代码，当您使用 -march=skylake-avx512 或在此类机器上使用 -march=native 进行编译时。
在我的代码中，我发现处理器大部分时间都花在下面显示的函数上。循环的objective就是要找出满足循环内条件的val1值。变量 Val1 和 a 的类型为 long long int（64 位）。而且，它们是在函数内部声明的局部非静态变量。
long long int findval(long long int x)
{
long long int Val1,a=x;
for (Val1 = 63; Val1 > 22; Val1--)
{
if (((a >> Val1) & 1) == 1)
break;
}
return Val1;
}
还有其他simple/optimized方法可以找出 Val1 值吗？
首先，请记住，仅仅因为您发现处理器大部分时间都花在那个 function 片段上，并不意味着有片段的问题。也许您应该尝试找出为什么您的代码如此频繁地调用该代码段。
其次，既然你是来这里寻求帮助的，你不妨向我们展示你所拥有的一切，而不是你所拥有的一部分你认为应该足以让我们找出问题所在的子集。最重要的是，你真的应该向我们展示你的变量是如何声明的以及它们的确切位置声明。它们是局部函数吗？他们是static吗？会不会是你声明了一些东西volatile？没有什么是无关紧要的，一切都很重要。
无论如何，如果我们假设代码段可以优化，那么我会说以下内容：
您的 Val1 应该 而不是 是 long long int，因为它的值仅在23 和 63。因此，它应该是 int。
（如果由于某些原因 Val1 必须 计算为 long long int，然后尝试转换它到循环之前类型为 int 的另一个变量，并在循环中使用该变量。）
如果您尝试这样做，那么编译器可能能够弄清楚您正在尝试做的是找到位范围内的第一个非零位，并用一条机器指令替换整个循环.
警告：我的回答写错了（右边第一位），抱歉。无论如何，这些方法可以很容易地适应 MSb。
您可以通过查找来简化流程 table。您预先计算了从 0 到 2^k-1 的所有数字最右边位的索引。您将一次处理 k 位的切片中的数字，并尝试从右到左切片，直到切片不为零。
一个有趣的选择是将 long long 映射到一个八字节的数组；字节对应于 256 个条目的 lookup-table。这样，您就可以直接按字节寻址。
也可以通过 shorts 进行处理，但代价是 65536 (64K) 个条目的 LUT。最佳可能介于两者之间。有缓存效果。
另一种有用的方法是二分法：屏蔽掉 32 位高位（或加载低位 int）并测试零。然后用非零部分屏蔽掉高 16 位，依此类推。最后，使用 LUT 技巧。只需 3 步，您就可以从 64 人减少到 8 人。
如果比特索引的分布是均匀的，这是合适的。如果偏向于小值，顺序搜索还是可以的。
如果你可以使用 GCC intrisic 那么你可以尝试这样的事情
请注意，这里假定 x 不为 0，因为当 x 为 0
时__builtin_clzll() 的结果未定义
#include <limits.h>
long long int findval(long long int x)
{
// Get size of long long in bits
size_t llsize = sizeof(long long) * CHAR_BIT;
// Subtract count of leading zeros from size of long long
return llsize - __builtin_clzll(x);
}
出于某种原因，我认为这在某些时候被标记为 x86 and/or x86-64。我的 GNU C 答案适用于任何 ISA，但我专注于 MSVC 的 x86 特定内在函数，以及它如何使用 GCC/clang 为 x86 编译。不幸的是，没有一种完全可移植的方法可以有效地执行此操作，因此 绝对值得做一些 #ifdef 以利用 HW 对您关心的目标上的此操作的支持。
您似乎想要 max(22, 63 - clz(x))，其中 clz 是一些计数前导零函数。例如在 GNU C 中，__builtin_clzll()。 63-clz(x) 是 MSB 的位置，当 long long = int64_t 就像在 x86 上一样。
您的 Val1 > 22 循环条件在 Val1 = 22 处变为假，因此如果到那时没有找到设置位，这就是非 break 退出循环的方法。
__builtin_clzll 在其输入为零 (
#include <limits.h>
inline
int MSB_position_clamped (long long x)
{
int maxpos = CHAR_BIT * sizeof(x) - 1;
x |= 1LL << 22; // avoid x==0 UB and make clz at least 22
return maxpos - __builtin_clzll(x);
}
对于 MSVC，您需要 _BitScanReverse64（在 AMD 上速度较慢）或 63 - _mm_lzcnt_u64（需要 BMI1）。 _mm 内部版本可用于所有 x86-64 编译器。
（正如 Mike 指出的那样，移位计数只需要 int。更宽的移位计数没有帮助，尤其是在为 long long 需要 2 个寄存器的 32 位机器编译时）。
这对 x86-64 编译效率很高，尤其是使用 clang (Godbolt)。我们还希望它能够有效地内联到这 2 条指令。
# clang 9.0 -O3 for x86-64 System V
MSB_position_clamped:
or rdi, 4194304
bsr rax, rdi
ret
(x86 传统位扫描指令直接找到位位置，如您所愿。BMI1 lzcnt 在 AMD 上速度更快，但实际上计算前导零，因此您需要从类型宽度中减去它. 即使 GCC 使用 BSR，它也无法将 63 - clz 优化回 BSR；它翻转了两次。）
请注意，即使只有 重要 位较低，负 2 的补码整数也会设置其 MSB。你确定你想要一个签名类型吗？
如果是这样，您确定不需要 GNU C __builtin_clrsbll？ （Returns x 中的前导冗余符号位数，即最高有效位之后与其相同的位数）没有单个 x86 指令，但我假设它通过 ~x 上的位扫描有效地完成它并以某种方式组合。
此外，如果您的原始代码旨在完全移植到所有 ISO C 实现，我不确定是否保证符号位移动到较低的位位置。我不希望它在 sign/magnitude C 实现中用于带符号的右移。 （ISO C 将有符号整数类型的右移是逻辑运算还是算术运算留给实现；理智/高质量的实现选择算术。使用 2 的补码整数，您的代码将以任何一种方式工作；您不关心它是否向零移动或符号位的副本。）
许多 CPU（不仅仅是 x86）有 bit-scan instructions 在一条硬件指令中执行此操作，但据我所知无法编写 可移植 C 将编译成这样的指令。 ISO C 没有费心去添加可以使用此类指令（当它们存在时）的标准函数。 所以唯一好的选择是特定于编译器的扩展。（一些编译器确实识别 popcount 循环，但是当你的循环停止在 22 而不是 0 时，它不太可能适合 CLZ 的模式如果任何编译器都在寻找它，就可以识别它。）有些语言在这方面比 C 更好，特别是 Rust 具有设计非常好的包括位扫描的整数原语。
GNU C __builtin_clzll() 在有硬件指令的 ISA 上编译为硬件指令，否则回退到调用库函数。 （IDK 回退的效率如何；它可能一次使用一个字节或半字节 LUT 而不是简单的移位。）
在 32 位 x86 上，__builtin_clzll 在低半部分和高半部分使用 bsr 并将结果与 cmov 或分支组合。 _BitScanReverse64 和 _mm_lzcnt_u64 等纯内在函数在 32 位模式下不可用，因此如果您使用内在函数而不是 GNU C "portable" 内置函数，则必须自己做。
32 位代码不如 64 位代码好，但它仍然是非循环的。 （而且你的循环变得非常低效；GCC 不会 "think of" 在低 32 位之前在单独的循环中尝试高 32 位，所以它必须 shrd / sar 然后 cmov 基于移位计数超过 32 的位测试。(Godbolt)。Clang 仍然完全展开，并且确实利用了只测试相关数字的一半。
由于您标记了此 SIMD，x86 AVX512CD 实际上在一个向量寄存器中的 2、4 或 8x int64_t 元素上有一条 lzcnt 指令：vplzcntq.内在是 __m512i _mm512_lzcnt_epi64(__m512i a);.
所有支持 AVX512 的真实 CPU 都有 AVX512CD。
在 Skylake-X 和 Ice Lake 上，它解码为具有 4 个周期延迟、0.5 个时钟吞吐量的单个 uop。 (https://uops.info/)。 （看起来它与 FMA/mul/add FP 指令在相同的端口上运行，可能使用相同的硬件来规范化浮点尾数，该操作也需要找到 MSB。）
因此，希望 GCC 和 clang 可以自动向量化使用 __builtin_clzll 的代码，当您使用 -march=skylake-avx512 或在此类机器上使用 -march=native 进行编译时。