设置的最小有效位的位置

Question

设置的最小有效位的位置

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

一个简单的实现是：

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

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

有什么办法能挤出一些循环吗？

(注意：这个问题是给喜欢这类事情的人，而不是为了让人们告诉我木偶优化是邪恶的。)

Answer 1

旋转钻头提供了一个优秀的集合，呃，比特旋转黑客，并附上性能/优化讨论。对于您的问题，我最喜欢的解决方案(来自该站点)是“乘和查找”：unsigned int v;  // find the number of trailing zeros in 32-bit v int r;           // result goes herestatic 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];有用的参考资料："用deBruijn序列索引计算机单词中的a 1“-解释上述代码的工作原理。"板代表>比特板>BitScan“-详细分析这一问题，特别侧重于国际象棋编程。

Answer 2

为什么不使用内置的FFS？(我从Linux上抓取了一个手册页，但它比这更广泛。)FFS(3)-Linux手册页名字，姓名FFS-查找一个单词中的第一个位简介#include&nbsp;<strings.h>int&nbsp;ffs(int&nbsp;i);#define&nbsp;_GNU_SOURCE#include&nbsp;<string.h>int&nbsp;ffsl(long&nbsp;int&nbsp;i);int&nbsp;ffsll(long&nbsp;long&nbsp;int&nbsp;i);描述函数返回在字I中设置的第一个(最不重要的)位的位置。最不重要的位是位置1和最重要的位置，例如32或64。函数ffsll()和ffsl()做同样的工作，但使用可能不同大小的参数。返回值这些函数返回第一个位集的位置，如果i中没有设置位，则返回0。符合4.3BSD，POSIX.1-2001。注记BSD系统有一个原型<string.h>.

Answer 3

有x86程序集指令(bsf)那就行了。*)更优化？！边注：这个级别的优化本质上是依赖于体系结构的。今天的处理器是太复杂(在分支预测、缓存丢失、流水线方面)，很难预测哪段代码在哪种体系结构上执行得更快。将操作从32减少到9或类似的事情甚至会降低某些体系结构的性能。单个体系结构上的优化代码可能会导致另一个体系结构中更糟的代码。我认为您可以为特定的CPU优化它，或者保留它的原样，让编译器来选择它认为更好的。