找到一个二元数的 1 的索引，它是 2 的幂

Question

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

Answer 1

以下是对@Juan Lopez和@njuffa提供的答案的O(1)代码中使用de Bruijn 序列背后的逻辑的解释（顺便说一句，很棒的答案，您应该考虑对它们进行投票）。

de Bruijn 序列

给定字母K和长度n，de Bruijn 序列是来自K的字符序列，其中包含（无特定顺序）其中长度为n 的所有排列[1]，例如，给定字母{a, b}并且n = 3，以下是长度为 3的{a, b} 的所有排列（带重复）的列表：

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

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

“babbbaaa”是我们字母表K = {a, b}和 n = 3的 de Bruijn 序列，表示它的符号是B(2, 3)，其中 2 是K的大小，也表示为k。序列的大小由k ⁿ给出，在前面的例子中k ⁿ = 2 ³ = 8

我们如何构造这样的字符串？一种方法包括构建一个有向图，其中每个节点代表一个排列，并且对于字母表中的每个字母都有一个输出边，从一个节点到另一个节点的转换将边字母添加到下一个节点的右侧并删除其最左边的字母。一旦图被建立起来，抓住它上面的哈密​​顿路径中的边来构造序列。

上一个示例的图形将是：

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

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

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

我们可以从节点开始，bbb在这种情况下，获得的序列将是“aaabbabbb”。

现在覆盖了 de Bruijn 序列，让我们使用它来查找整数中前导零的数量。

de Bruijn 算法 [2]

要找出整数值中前导零的数量，该算法的第一步是从右到左隔离第一位，例如，给定 848 (1101010000 ₂ )：

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

一种方法是使用x & (~x + 1)，您可以在Hacker's Delight 书（第 2 章第 2-1 节）中找到有关此表达式如何工作的更多信息。

问题指出输入是 2 的幂，所以最右边的位从一开始就被隔离，不需要任何努力。

一旦该位被隔离（因此将其转换为 2 的幂），第二步包括使用散列表方法及其散列函数将过滤后的输入与其相应数量的前导 0 pe 映射，应用散列函数h(x) to 0000010000 ₂应该返回包含值 4 的表的索引。

该算法建议使用完美的哈希函数来突出这些属性：

• 哈希表应该很小
• 哈希函数应该易于计算
• 散列函数不应产生冲突，即h(x)？h(y)如果x ? 是

为了实现这一点，我们可以使用 de Bruijn 序列，其二进制元素字母表K = {0, 1}，如果我们想解决 64 位整数的问题，则n = 6（对于 64 位整数，有 64需要两个值的可能幂和 6 位来计算它们）。B(2, 6) = 64，所以我们需要找到一个长度为 64 的 de Bruijn 序列，它包括长度为 6 (000000 ₂ , 000001 ₂ , ..., 111111 ₂ )的二进制数字的所有排列（带重复）。

使用实现上述方法的程序，您可以生成满足 64 位整数要求的 de Bruijn 序列：

0000011111101101110101011110010110011010010011100010100011000010 ₂ = 7EDD5E59A4E28C2 ₁₆

该算法的建议散列函数为：

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

哪里x是二的幂。对于 64 位内的每个可能的 2 次幂，h(x)返回相应的二进制排列，我们需要将这些排列中的每一个与前导零的数量相关联以填充表。例如，如果x是 16 = 10000 ₂，它有 4 个前导零，我们有：

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

因此，在表的索引 31 处，我们存储 4。 另一个示例，让我们使用 256 = 100000000 ₂，它有 8 个前导零：

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

在索引 59 处，我们存储 8。我们对每个 2 的幂重复此过程，直到填满表。手动生成表格很笨拙，您应该使用类似于此处找到的程序来完成这项工作。

最后我们会得到下表：

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

以及计算所需值的代码：

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

什么保证我们不会因碰撞而丢失 2 的幂的索引？

散列函数基本上得到de Bruijn序列中包含的每2次幂的每6位排列，乘以x基本上只是向左移动（将数字乘以2的幂与左移数字相同） ，然后应用右移 58，将 6 位组一个一个地隔离，x由于 de Bruijn 序列，两个不同的值（此问题所需散列函数的第三个属性）不会出现冲突。

参考：

[1] De Bruijn 序列- http://datagenetics.com/blog/october22013/index.html

[2] 使用 de Bruijn 序列索引计算机单词中的 1 - http://supertech.csail.mit.edu/papers/debruijn.pdf

[3] 神奇的比特扫描- http://elemarjr.net/2011/01/09/the-magic-bitscan/