假设我有一个数x,它是2的幂次方,也就是说x = 2^i (i为整数)。 那么x的二进制表示中只有一个'1'。我需要找到那个'1'的下标。 例如,x = 16 (十进制) x = 10000 (二进制) 这里的下标应该是4。通过位运算在O(1)时间内是否能找到下标呢?
假设我有一个数x,它是2的幂次方,也就是说x = 2^i (i为整数)。 那么x的二进制表示中只有一个'1'。我需要找到那个'1'的下标。 例如,x = 16 (十进制) x = 10000 (二进制) 这里的下标应该是4。通过位运算在O(1)时间内是否能找到下标呢?
[aaa, aab, aba, abb, baa, bab, bba, bbb]
前面示例的图表如下:
然后,取一个哈密顿路径(即访问每个顶点恰好一次的路径):从节点 aaa
开始,沿着每条边走,我们最终得到:
(aaa) -> b -> a -> b -> b -> b -> a -> a -> a (aaa) = babbbaaa
bbb
开始,这样得到的序列将是“aaababbb”。 isolate rightmost bit
1101010000 ---------------------------> 0000010000
x&(~x + 1)
,您可以在 Hacker's Delight book(第2章第2-1节)中找到有关此表达式如何工作的更多信息。为了实现这一点,我们可以使用 de Bruijn 序列,其中二进制元素的字母表为 K = {0, 1},如果我们要解决 64 位整数的问题,则 n = 6(对于 64 位整数,有 64 种可能的二的幂值,需要 6 个位来计数所有这些值)。B(2, 6) = 64,因此我们需要找到一个长度为 64 的 de Bruijn 序列,其中包括长度为 6 的二进制数字的所有排列(0000002,0000012,...,1111112)。
使用像上面描述的方法实现的程序,您可以生成满足 64 位整数要求的 de Bruijn 序列:
00000111111011011101010111100101100110100100111000101000110000102 = 7EDD5E59A4E28C216
该算法的建议哈希函数为:
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)
h(256) = (256 * 0x7EDD5E59A4E28C2) >> 58
= 17137856407927308800 (due to overflow) >> 58
= 59 (111011b)
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的幂次方索引的情况不会发生?
哈希函数基本上获取每个2的幂次方包含在de Bruijn序列中的每个6位排列,乘以x
基本上只是向左移位(将一个数乘以2的幂次方等同于左移该数字),然后应用右移58,逐个隔离6位组,对于两个不同的x
值不会出现碰撞(这个问题的期望哈希函数的第三个属性)由于de Bruijn序列。
[1] 德布鲁因序列 - http://datagenetics.com/blog/october22013/index.html
[2] 使用德布鲁因序列在计算机字中索引1 - http://supertech.csail.mit.edu/papers/debruijn.pdf
[3] 魔术位扫描 - http://elemarjr.net/2011/01/09/the-magic-bitscan/
lambda(x)
进行二进制搜索),然后滥用字的宽度以并行计算其余部分(由于第一步,字比正在处理的值宽得多,因此它可以在字中多次拟合以进行并行工作)。 - harold#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;
}
bit_pos()
在 i=0,..31 时的 2**i。我使用两个不同的编译器编译了代码,并且测试通过。你在哪个值上看到 bit_pos()
返回了错误的结果? - njuffa#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;
}
}
n & (~n + 1)
,因为问题已经保证只有一个位被设置。 - harold答案是......是的!
仅出于娱乐目的,因为您在其中一个答案下面评论说 i
最多到 20 就足够了。
(这里的乘法只有 0 或 1 的情况)
#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
}
}
log_2(x)
(5个字符) - amit