如何有效地找到整数中最低有效设置位的位置？

确定最低有效设置位的位置

在编程中，确定设置的最低有效位（LSB）的位置整数可能是一个有用的运算。一个简单的实现涉及重复用 1 掩码整数并将其右移，直到结果变为非零，但此方法对于大整数可能会很慢。

位旋转优化

位摆弄黑客提供了一种有效的替代方案。其中一种黑客称为“乘法和查找”方法，利用 de Bruijn 序列的属性在一步中执行计算。

代码实现

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

说明

此代码的工作原理是乘以整数v 乘以一个神奇的常数，然后对结果进行位移。 MultiplyDeBruijnBitPosition 数组将乘法结果映射到 LSB 的所需位置。

优点和参考

此方法比普通实现要快得多，特别是对于大整数。有关此技术的更多见解和详细说明，请参阅：

• “使用 de Bruijn 序列在计算机单词中索引 1”
• “板表示 > 位板 >位扫描”

以上是如何有效地找到整数中最低有效设置位的位置？的详细内容。更多信息请关注PHP中文网其他相关文章！