algorithm - 找到二进制数1的索引，即2的幂

Question

假设我有一个数x，它是2的幂，这意味着x=2^i。
所以x的二进制表示只有一个“1”。我需要找到那个的索引。
例如，x=16（十进制）
X=10000（二进制）
这里的索引应该是4仅仅使用位运算就可以在O（1）时间内找到索引吗？

Answer 1

以下是对de Bruijn sequences和@Juan Lopez提供的答案的O（1）代码中使用@njuffa背后的逻辑的解释（顺便说一下，您应该考虑对它们进行升级）。
德布鲁因序列
给定一个字母K和一个长度n，de Bruijn序列是K中的一个字符序列，其中包含（没有特定顺序）所有长度为n的置换[1]，例如，给定字母{a，b}和n=3，以下是长度为3的{a，b}的所有置换（带重复项）的列表：

 [aaa, aab, aba, abb, baa, bab, bba, bbb]

为了创建相关的de Bruijn序列，我们构造了一个包含所有这些不重复排列的最小字符串，其中一个字符串是：babbaaa

“babbaaa”是我们的字母k={a，b}和n=3的de bruijn序列，表示这一序列的符号是b（2，3），其中2是k的大小，也表示为k。在前面的示例中，序列的大小由kn给出，kn=23=8
我们怎么能构造这样一个字符串？一种方法是建立一个有向图，其中每个节点表示一个置换，并且对于字母表中的每个字母都有一个传出边，从一个节点到另一个节点的转换将边字母添加到下一个节点的右侧，并删除其最左的字母一旦建立了图，抓住它上面的a Hamiltonian path中的边来构造序列。

上一个示例的图表为：

然后，选择一条哈密顿路径（一条只访问每个顶点一次的路径）：

从node aaa开始，沿着每条边，我们最终得到：

(aaa) -> b -> a -> b -> b -> b -> a -> a -> a (aaa) = babbbaaa

我们可以从节点 bbb开始，在这种情况下，获得的序列将是“aaabbbb”。
现在已经覆盖了de bruijn序列，让我们使用它来查找整数中前导零的数目。
德布鲁因算法[2]
为了找出整数值中前导零的数目，该算法的第一步是将第一位从右到左隔离，例如给定848（11010100002）：

              isolate rightmost bit     
1101010000 ---------------------------> 0000010000

一种方法是使用 x & (~x + 1)，您可以在 Hacker's Delight book（第2章，第2-1节）中找到有关此表达式如何工作的更多信息。
问题是输入是2的幂，所以最右边的位从一开始就被隔离了，不需要付出任何努力。
一旦该位被隔离（从而将其转换为2的幂），第二步包括使用哈希表方法及其哈希函数将过滤后的输入与其对应的前导0的数目映射，即，将哈希函数h（x）应用于00000100002应返回包含值4的表上的索引。
算法建议使用a perfect hash function来突出显示这些属性：
哈希表应该很小
哈希函数应该易于计算
哈希函数不应产生冲突，即，如果x≠y，则h（x）≠h（y）
为了实现这一点，我们可以使用一个de bruijn序列，它的字母表是二进制元素k={0，1}，如果我们想解决64位整数的问题（对于64位整数，两个值有64个可能的幂，需要6位来计算它们）。b（2，6）=64，所以我们需要找到一个长度为64的de bruijn序列，它包括长度为6（0000002000012，…，111111 2）的二进制数字的所有置换（带重复）。
使用实现上述方法的程序，可以生成满足64位整数要求的de bruijn序列：
0000011111101110110101110100101100110011010011100010110000102=7EDD5E59A4 E28C216
该算法的哈希函数为：

h(x) = (x * deBruijn) >> (k^n - n)

其中 x是2的幂。对于64位内2的每一个可能幂，h（x）返回一个对应的二进制置换，我们需要将这些置换中的每一个与前导零的数目相关联以填充表例如，如果 x是16=100002，它有4个前导零，则我们有：

h(16) = (16 * 0x7EDD5E59A4E28C2) >> 58
      = 9141566557743385632 >> 58
      = 31 (011111b)

所以，在表的索引31处，我们存储4。另一个例子，我们使用256=1000000002，它有8个前导零：

h(256) = (256 * 0x7EDD5E59A4E28C2) >> 58
       = 17137856407927308800 (due to overflow) >> 58
       = 59 (111011b)

在索引59处，我们存储8我们对每两个幂重复这个过程，直到填满表格。手工生成表是很困难的，您应该使用一个 like the one found here程序来完成这项工作。
最后我们将得到下表：

int table[] = {
      63,  0, 58,  1, 59, 47, 53,  2, 
      60, 39, 48, 27, 54, 33, 42,  3,
      61, 51, 37, 40, 49, 18, 28, 20,
      55, 30, 34, 11, 43, 14, 22,  4,
      62, 57, 46, 52, 38, 26, 32, 41,
      50, 36, 17, 19, 29, 10, 13, 21,
      56, 45, 25, 31, 35, 16,  9, 12,
      44, 24, 15,  8, 23,  7,  6,  5
};

以及计算所需值的代码：

// Assumes that x is a power of two
int numLeadingZeroes(uint64_t x) { 
    return table[(x * 0x7EDD5E59A4E28C2ull) >> 58];
}

什么保证我们不会因为碰撞而丢失二次幂的索引？
hash函数基本上得到de Bruijn序列中包含的每6位置换，对于2的每一次幂，乘 x基本上只是向左移位（乘2的幂等于 left shifting the number），然后应用右移位58，将6位组逐个隔离由于de-bruijn序列，两个不同的 x值（此问题所需哈希函数的第三个属性）不会出现冲突。
参考文献：
[1]de bruijn序列- http://datagenetics.com/blog/october22013/index.html
[2]使用de Bruijn序列在计算机单词中索引a 1- http://supertech.csail.mit.edu/papers/debruijn.pdf
[3]神奇的比特扫描- http://elemarjr.net/2011/01/09/the-magic-bitscan/