c++ - 如何找到 n，其中 k = 2^n

Question

这个问题已经有答案了:

Position of least significant bit that is set (23 个回答)

已关闭 8 年前。

如果我知道一个整数 k = 2^n ，如何高效找到n ？换句话说，如果我知道设置了整数中的单个位，那么如何获取该位的位置？

一个想法是找到 k-1 的汉明权重但是还有其他我没有想到的更简单的方法吗？

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

This page提供了对问题的详 segmentation 析，重点是国际象棋编程。

答案复制自here 。PS:不知道如何在这个问题上感谢作者，所以就这样写了。