我正在寻找一种有效的方法来确定以整数设置的最低有效位的位置,例如对于 0x0FF0,它将是 4。
一个简单的实现是这样的:
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
任何想法如何挤出一些周期?
(注意:这个问题是给喜欢这些东西的人准备的,而不是让人们告诉我 xyzoptimization 是邪恶的。)
[编辑]感谢大家的想法!我也学到了一些其他的东西。酷!
最佳答案
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 析,特别关注国际象棋编程
关于c++ - 设置的最低有效位的位置,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/757059/