设置的最低有效位的位置

Question

我正在寻找一种有效的方法来确定以整数设置的最低有效位的位置，例如对于 0x0FF0，它将是 4。

一个简单的实现是这样的：

 unsigned GetLowestBitPos(unsigned value)
{
   assert(value != 0); // handled separately

   unsigned pos = 0;
   while (!(value & 1))
   {
      value >>= 1;
      ++pos;
   }
   return pos;
}

任何想法如何挤出一些周期？

（注意：这个问题是给喜欢这些东西的人准备的，而不是让人们告诉我 xyzoptimization 是邪恶的。）

[编辑] 感谢大家的想法！我也学到了一些其他的东西。凉爽的！

原文由 peterchen 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

Bit Twiddling Hacks 提供了一个很好的，呃，bit twiddling hacks 的集合，并附有性能/优化讨论。对于您的问题，我最喜欢的解决方案（来自该站点）是«乘法和查找»：

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

有用的参考资料：

• “ Using de Bruijn Sequences to Index a 1 in a Computer Word ” - 解释上述代码为何有效。
• “ Board Representation > Bitboards > BitScan ” - 详细分析这个问题，特别关注国际象棋编程

原文由 Anton Tykhyy 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

11 年后，我们终于有了 count_zero ！

 #include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    for (const std::uint8_t i : { 0, 0b11111111, 0b00011100, 0b00011101 }) {
        std::cout << "countr_zero( " << std::bitset<8>(i) << " ) = "
                  << std::countr_zero(i) << '\n';
    }
}

干得好 C++20

原文由 Surt 发布，翻译遵循 CC BY-SA 4.0 许可协议