找到二进制数 1 的索引，它是 2 的幂
find the index of 1 of a binay number which is power of 2
假设我有一个数字 x，它是 2 的幂，这意味着对于某些 i，x = 2^i。
所以 x 的二进制表示只有一个 '1'。我需要找到那个索引。
例如，x = 16（十进制）
x = 10000（二进制）
这里的索引应该是4。是否可以只用位运算在O(1)时间内找到索引？
这取决于你的定义。首先让我们假设有 n 位，因为如果我们假设有一个常数位数，那么我们可能用它们做的所有事情都将花费常数时间，所以我们无法比较任何东西。
首先，让我们从尽可能广泛的角度来看待 "bitwise operations" - 它们对位进行运算，但不一定按点进行运算，此外，我们将对运算进行计数，但不包括运算本身的复杂性。
米。 L. Fredman 和 D. E. Willard 表明有一个 O(1) 运算的算法来计算 lambda(x)（x 的以 2 为底的对数的下限，因此是最高设置位的索引） .虽然它包含很多乘法，所以按位调用它有点有趣。
另一方面，有一个明显的 O(log n) 运算算法，不使用乘法，只是对其进行二进制搜索。但是可以做得更好，Gerth Brodal 表明它可以在 O(log log n) 操作中完成（其中 none 是乘法）。
我引用的所有算法都在 The Art of Computer Programming 4A, bitwise tricks and techniques.
None 其中的
None 确实符合在恒定时间内找到 1 的条件，很明显您不能那样做。尽管他们声称，其他答案也不符合条件。它们很酷，但它们是为特定的常数位数设计的，因此任何天真的算法也将是 O(1)（平凡的，因为没有 n 可以依赖）。在评论中，OP 说了一些暗示他实际上想要的东西，但从技术上讲并没有回答这个问题。
问题的详细说明我不是很清楚。例如，哪些操作算作 "bit operations" 以及有多少位构成了相关输入？许多处理器有一个 "count leading zeros" 或 "find first bit" 指令通过内部公开，基本上直接提供所需的结果。
下面我将展示如何根据 De Bruijn sequence.
查找 32 位整数中的位位置
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/* find position of 1-bit in a = 2^n, 0 <= n <= 31 */
int bit_pos (uint32_t a)
{
static int tab[32] = { 0, 1, 2, 6, 3, 11, 7, 16,
4, 14, 12, 21, 8, 23, 17, 26,
31, 5, 10, 15, 13, 20, 22, 25,
30, 9, 19, 24, 29, 18, 28, 27};
// return tab [0x04653adf * a >> 27];
return tab [(a + (a << 1) + (a << 2) + (a << 3) + (a << 4) + (a << 6) +
(a << 7) + (a << 9) + (a << 11) + (a << 12) + (a << 13) +
(a << 16) + (a << 18) + (a << 21) + (a << 22) + (a << 26))
>> 27];
}
int main (void)
{
uint32_t nbr;
int pos = 0;
while (pos < 32) {
nbr = 1U << pos;
if (bit_pos (nbr) != pos) {
printf ("!!!! error: nbr=%08x bit_pos=%d pos=%d\n",
nbr, bit_pos(nbr), pos);
EXIT_FAILURE;
}
pos++;
}
return EXIT_SUCCESS;
}
如果允许单个内存访问，则可以在 O(1) 中完成：
#include <iostream>
using namespace std;
int indexes[] = {
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
};
int main() {
unsigned long long n;
while(cin >> n) {
cout << indexes[((n & (~n + 1)) * 0x07EDD5E59A4E28C2ull) >> 58] << endl;
}
}
而答案是………………是的！
纯属娱乐，因为您在其中一个答案下方评论说 i 最多 20 个就足够了。
（这里的乘法不是零就是一）
#include <iostream>
using namespace std;
int f(int n){
return
0 | !(n ^ 1048576) * 20
| !(n ^ 524288) * 19
| !(n ^ 262144) * 18
| !(n ^ 131072) * 17
| !(n ^ 65536) * 16
| !(n ^ 32768) * 15
| !(n ^ 16384) * 14
| !(n ^ 8192) * 13
| !(n ^ 4096) * 12
| !(n ^ 2048) * 11
| !(n ^ 1024) * 10
| !(n ^ 512) * 9
| !(n ^ 256) * 8
| !(n ^ 128) * 7
| !(n ^ 64) * 6
| !(n ^ 32) * 5
| !(n ^ 16) * 4
| !(n ^ 8) * 3
| !(n ^ 4) * 2
| !(n ^ 2);
}
int main() {
for (int i=1; i<1048577; i <<= 1){
cout << f(i) << " "; // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
}
}
以下是对 de Bruijn sequences in the O(1) code of the answers provided by @Juan Lopez and @njuffa 使用背后逻辑的解释（顺便说一句，很好的答案，您应该考虑对它们投赞成票）。
de Bruijn 序列
给定字母表 K 和长度 n，de Bruijn 序列 是来自 K 的字符序列，其中包含（无特定顺序）长度为 n 的所有排列 [1]，例如，给定字母表{a, b} and n = 3, 下面是{a, b} 长度为 3:
[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.序列的大小由kn给出，在前面的例子中kn = 23 = 8
我们如何构建这样的字符串？ 一种方法是构建一个有向图，其中每个节点代表一个排列，并且字母表中的每个字母都有一个出边，即从一个节点到另一个节点的转换将边缘字母添加到下一个节点的右侧并删除其最左边的字母。构建图形后，抓住 Hamiltonian path 中的边以构建序列。
上一个示例的图形为：
然后，采用哈密顿路径（访问每个顶点恰好一次的路径）：
从节点 aaa 开始，沿着每条边，我们最终得到：
(aaa) -> b -> a -> b -> b -> b -> a -> a -> a (aaa) = babbbaaa
我们可以从节点 bbb 开始，在这种情况下，获得的序列将是“aaababbb”。
既然已经介绍了 de Bruijn 序列，让我们用它来查找整数中前导零的个数。
de Bruijn 算法 [2]
要找出整数值中前导零的个数，该算法的第一步是从右到左隔离第一位，例如，给定 848 (11010100002):
isolate rightmost bit
1101010000 ---------------------------> 0000010000
一种方法是使用 x & (~x + 1)，您可以在 Hacker's Delight book（第 2 章，第 2-1 节）中找到有关此表达式如何工作的更多信息。
问题说输入是2的幂，所以最右边的位从一开始就被隔离了，不需要任何努力。
一旦该位被隔离（从而将其转换为 2 的幂），第二步包括使用散列 table 方法及其散列函数将过滤后的输入与其对应的数字进行映射前导 0，p.e.，将哈希函数 h(x) 应用于 00000100002 应该 return 索引在包含值 4.
的 table 上
该算法建议使用 perfect hash function 突出显示这些属性：
- 散列 table 应该很小
- 散列函数应该很容易计算
- 散列函数不应产生冲突，即 h(x) ≠ h(y) if x ≠ y
为了实现这一点，我们可以使用 de Bruijn 序列，其中包含二进制元素的字母表 K = {0, 1} ，如果我们想解决 64 位整数的问题，则 n = 6（对于 64 位整数，两个值有 64 种可能的幂，需要 6 位来计算它们） . B(2, 6) = 64，所以我们需要找到一个长度为 64 的 de Bruijn 序列，它包括长度为 6 (000000[=145) 的二进制数字的所有排列（有重复） =]2, 0000012, ..., 1111112).
使用实现上述方法的程序，您可以生成满足 64 位整数要求的 de Bruijn 序列：
00000111111011011101010111100101100110100100111000101000110000102 = 7EDD5E59A4E28C216
建议的算法哈希函数是：
h(x) = (x * deBruijn) >> (k^n - n)
其中 x 是二的幂。对于 64 位内每一个可能的 2 的幂，h(x) returns 一个对应的二进制排列，我们需要将这些排列中的每一个与前导零的数量相关联填写table。例如，如果 x 是 16 = 100002，它有 4 个前导零，我们有：
h(16) = (16 * 0x7EDD5E59A4E28C2) >> 58
= 9141566557743385632 >> 58
= 31 (011111b)
因此，在我们 table 的索引 31 处，我们存储 4。另一个例子，让我们使用 256 = 1000000002，它有 8 个前导零：
h(256) = (256 * 0x7EDD5E59A4E28C2) >> 58
= 17137856407927308800 (due to overflow) >> 58
= 59 (111011b)
在索引 59 处，我们存储 8。我们对 2 的每个幂重复此过程，直到填满 table。手动生成 table 很笨拙，您应该使用一个程序 like the one found here 来完成这项工作。
最后我们会得到以下 table:
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];
}
什么保证我们不会因为碰撞而丢失 2 的幂的索引？
散列函数基本上是获取de Bruijn序列中包含的每6位排列的每个2的幂，乘以x基本上只是向左移位（将数字乘以的幂two 等同于left shifting the number)，然后右移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/
假设我有一个数字 x，它是 2 的幂，这意味着对于某些 i，x = 2^i。 所以 x 的二进制表示只有一个 '1'。我需要找到那个索引。 例如，x = 16（十进制） x = 10000（二进制） 这里的索引应该是4。是否可以只用位运算在O(1)时间内找到索引？
这取决于你的定义。首先让我们假设有 n 位，因为如果我们假设有一个常数位数，那么我们可能用它们做的所有事情都将花费常数时间，所以我们无法比较任何东西。
首先，让我们从尽可能广泛的角度来看待 "bitwise operations" - 它们对位进行运算，但不一定按点进行运算，此外，我们将对运算进行计数，但不包括运算本身的复杂性。
米。 L. Fredman 和 D. E. Willard 表明有一个 O(1) 运算的算法来计算 lambda(x)（x 的以 2 为底的对数的下限，因此是最高设置位的索引） .虽然它包含很多乘法，所以按位调用它有点有趣。
另一方面，有一个明显的 O(log n) 运算算法，不使用乘法，只是对其进行二进制搜索。但是可以做得更好，Gerth Brodal 表明它可以在 O(log log n) 操作中完成（其中 none 是乘法）。
我引用的所有算法都在 The Art of Computer Programming 4A, bitwise tricks and techniques.
None 其中的
None 确实符合在恒定时间内找到 1 的条件，很明显您不能那样做。尽管他们声称，其他答案也不符合条件。它们很酷，但它们是为特定的常数位数设计的，因此任何天真的算法也将是 O(1)（平凡的，因为没有 n 可以依赖）。在评论中，OP 说了一些暗示他实际上想要的东西，但从技术上讲并没有回答这个问题。
问题的详细说明我不是很清楚。例如，哪些操作算作 "bit operations" 以及有多少位构成了相关输入？许多处理器有一个 "count leading zeros" 或 "find first bit" 指令通过内部公开，基本上直接提供所需的结果。
下面我将展示如何根据 De Bruijn sequence.
查找 32 位整数中的位位置#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/* find position of 1-bit in a = 2^n, 0 <= n <= 31 */
int bit_pos (uint32_t a)
{
static int tab[32] = { 0, 1, 2, 6, 3, 11, 7, 16,
4, 14, 12, 21, 8, 23, 17, 26,
31, 5, 10, 15, 13, 20, 22, 25,
30, 9, 19, 24, 29, 18, 28, 27};
// return tab [0x04653adf * a >> 27];
return tab [(a + (a << 1) + (a << 2) + (a << 3) + (a << 4) + (a << 6) +
(a << 7) + (a << 9) + (a << 11) + (a << 12) + (a << 13) +
(a << 16) + (a << 18) + (a << 21) + (a << 22) + (a << 26))
>> 27];
}
int main (void)
{
uint32_t nbr;
int pos = 0;
while (pos < 32) {
nbr = 1U << pos;
if (bit_pos (nbr) != pos) {
printf ("!!!! error: nbr=%08x bit_pos=%d pos=%d\n",
nbr, bit_pos(nbr), pos);
EXIT_FAILURE;
}
pos++;
}
return EXIT_SUCCESS;
}
如果允许单个内存访问，则可以在 O(1) 中完成：
#include <iostream>
using namespace std;
int indexes[] = {
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
};
int main() {
unsigned long long n;
while(cin >> n) {
cout << indexes[((n & (~n + 1)) * 0x07EDD5E59A4E28C2ull) >> 58] << endl;
}
}
而答案是………………是的！
纯属娱乐，因为您在其中一个答案下方评论说 i 最多 20 个就足够了。
（这里的乘法不是零就是一）
#include <iostream>
using namespace std;
int f(int n){
return
0 | !(n ^ 1048576) * 20
| !(n ^ 524288) * 19
| !(n ^ 262144) * 18
| !(n ^ 131072) * 17
| !(n ^ 65536) * 16
| !(n ^ 32768) * 15
| !(n ^ 16384) * 14
| !(n ^ 8192) * 13
| !(n ^ 4096) * 12
| !(n ^ 2048) * 11
| !(n ^ 1024) * 10
| !(n ^ 512) * 9
| !(n ^ 256) * 8
| !(n ^ 128) * 7
| !(n ^ 64) * 6
| !(n ^ 32) * 5
| !(n ^ 16) * 4
| !(n ^ 8) * 3
| !(n ^ 4) * 2
| !(n ^ 2);
}
int main() {
for (int i=1; i<1048577; i <<= 1){
cout << f(i) << " "; // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
}
}
以下是对 de Bruijn sequences in the O(1) code of the answers provided by @Juan Lopez and @njuffa 使用背后逻辑的解释（顺便说一句，很好的答案，您应该考虑对它们投赞成票）。
de Bruijn 序列
给定字母表 K 和长度 n，de Bruijn 序列 是来自 K 的字符序列，其中包含（无特定顺序）长度为 n 的所有排列 [1]，例如，给定字母表{a, b} and n = 3, 下面是{a, b} 长度为 3:
[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.序列的大小由kn给出，在前面的例子中kn = 23 = 8
我们如何构建这样的字符串？ 一种方法是构建一个有向图，其中每个节点代表一个排列，并且字母表中的每个字母都有一个出边，即从一个节点到另一个节点的转换将边缘字母添加到下一个节点的右侧并删除其最左边的字母。构建图形后，抓住 Hamiltonian path 中的边以构建序列。
上一个示例的图形为：
然后，采用哈密顿路径（访问每个顶点恰好一次的路径）：
从节点 aaa 开始，沿着每条边，我们最终得到：
(aaa) -> b -> a -> b -> b -> b -> a -> a -> a (aaa) = babbbaaa
我们可以从节点 bbb 开始，在这种情况下，获得的序列将是“aaababbb”。
既然已经介绍了 de Bruijn 序列，让我们用它来查找整数中前导零的个数。
de Bruijn 算法 [2]
要找出整数值中前导零的个数，该算法的第一步是从右到左隔离第一位，例如，给定 848 (11010100002):
isolate rightmost bit
1101010000 ---------------------------> 0000010000
一种方法是使用 x & (~x + 1)，您可以在 Hacker's Delight book（第 2 章，第 2-1 节）中找到有关此表达式如何工作的更多信息。
问题说输入是2的幂，所以最右边的位从一开始就被隔离了，不需要任何努力。
一旦该位被隔离（从而将其转换为 2 的幂），第二步包括使用散列 table 方法及其散列函数将过滤后的输入与其对应的数字进行映射前导 0，p.e.，将哈希函数 h(x) 应用于 00000100002 应该 return 索引在包含值 4.
的 table 上该算法建议使用 perfect hash function 突出显示这些属性：
- 散列 table 应该很小
- 散列函数应该很容易计算
- 散列函数不应产生冲突，即 h(x) ≠ h(y) if x ≠ y
为了实现这一点，我们可以使用 de Bruijn 序列，其中包含二进制元素的字母表 K = {0, 1} ，如果我们想解决 64 位整数的问题，则 n = 6（对于 64 位整数，两个值有 64 种可能的幂，需要 6 位来计算它们） . B(2, 6) = 64，所以我们需要找到一个长度为 64 的 de Bruijn 序列，它包括长度为 6 (000000[=145) 的二进制数字的所有排列（有重复） =]2, 0000012, ..., 1111112).
使用实现上述方法的程序，您可以生成满足 64 位整数要求的 de Bruijn 序列：
00000111111011011101010111100101100110100100111000101000110000102 = 7EDD5E59A4E28C216
建议的算法哈希函数是：
h(x) = (x * deBruijn) >> (k^n - n)
其中 x 是二的幂。对于 64 位内每一个可能的 2 的幂，h(x) returns 一个对应的二进制排列，我们需要将这些排列中的每一个与前导零的数量相关联填写table。例如，如果 x 是 16 = 100002，它有 4 个前导零，我们有：
h(16) = (16 * 0x7EDD5E59A4E28C2) >> 58
= 9141566557743385632 >> 58
= 31 (011111b)
因此，在我们 table 的索引 31 处，我们存储 4。另一个例子，让我们使用 256 = 1000000002，它有 8 个前导零：
h(256) = (256 * 0x7EDD5E59A4E28C2) >> 58
= 17137856407927308800 (due to overflow) >> 58
= 59 (111011b)
在索引 59 处，我们存储 8。我们对 2 的每个幂重复此过程，直到填满 table。手动生成 table 很笨拙，您应该使用一个程序 like the one found here 来完成这项工作。
最后我们会得到以下 table:
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];
}
什么保证我们不会因为碰撞而丢失 2 的幂的索引？
散列函数基本上是获取de Bruijn序列中包含的每6位排列的每个2的幂，乘以x基本上只是向左移位（将数字乘以的幂two 等同于left shifting the number)，然后右移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/