c++ - 设置的最低有效位的位置

Question

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

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

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

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

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

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

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

Answer 1

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 "- 对这个问题的详 segmentation 析，特别关注国际象棋编程