问题描述
我要寻找一种有效的方法，以确定在一个整数设置最低显著位的位置，例如为0x0FF0这将是4。
I am looking for an efficient way to determine the position of the least significant bit that is set in an integer, e.g. for 0x0FF0 it would be 4.
一个简单的实现是这样的：
A trivial implementation is this:
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); // handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
任何想法如何挤一些循环出来的吗？
Any ideas how to squeeze some cycles out of it?
（注意：这个问题是该享受这样的事情，没有人告诉我xyzoptimization是邪恶的人。）
(Note: this question is for people that enjoy such things, not for people to tell me xyzoptimization is evil.)
感谢大家的想法！我学到了一些其他的东西了。太酷了！
[edit] Thanks everyone for the ideas! I've learnt a few other things, too. Cool!
推荐答案
提供了一个极好的收集的，呃，有点摆弄黑客，具有性能/优化的讨论附后。我最喜欢你的问题的解决方案（从该站点）是«繁殖，并查找»：
Bit Twiddling Hacks offers an excellent collection of, er, bit twiddling hacks, with performance/optimisation discussion attached. My favourite solution for your problem (from that site) is «multiply and lookup»:
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];
有用的参考资料：
Helpful references:
- 指数1 - 解释一下，为什么上述code ++工程。
- - 这个问题的详细分析，尤其侧重于国际象棋编程
- "Using de Bruijn Sequences to Index a 1 in a Computer Word" - Explanation about why the above code works.
- "Board Representation > Bitboards > BitScan" - Detailed analysis of this problem, with a particular focus on chess programming
这篇关于至少显著位的位置，它被设置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！