p**l
发帖数: 703 | 1 【 以下文字转载自 Programming 讨论区 】
发信人: pwcl (全世界无产者联合起来), 信区: Programming
标 题: 请教个算法问题
发信站: BBS 未名空间站 (Wed May 2 23:29:54 2018, 美东)
对一个 unsigned int, 找出所有bit 1 的位置
比如 5 =101， 输出 0，2
8 = 1000， 输出 3
能在O(n)时间内完成吗？这里 n 是bit 1 的个数 | v******s
发帖数: 144 | 2 烂问题，没意思
先把bit分开
int t = n&(-n) //参考binary index tree
再查表
unordered_map xxx{{1, 0}{2, 1}, {4, 2} .... )
vector bit_pos;
while(n)
{
int t = n & (-n);
n -= t;
bit_pos.push_back(xxx[t]);
}
【在 p**l 的大作中提到】
: 【 以下文字转载自 Programming 讨论区 】
: 发信人: pwcl (全世界无产者联合起来), 信区: Programming
: 标 题: 请教个算法问题
: 发信站: BBS 未名空间站 (Wed May 2 23:29:54 2018, 美东)
: 对一个 unsigned int, 找出所有bit 1 的位置
: 比如 5 =101， 输出 0，2
: 8 = 1000， 输出 3
: 能在O(n)时间内完成吗？这里 n 是bit 1 的个数
| o*******r
发帖数: 73 | 3 vector findOnes(unsigned n) {
vector ret;
for (int i = 0; i < 32; ++i) if (n & (1 << i)) ret.push_back(i);
return ret;
}
记得复杂度是当O趋近于无穷大的一个逼近，现在这个问题N最多也就32.
其实如果四位四位的存到表里面再的话，可以8次做完，那个应该是最快的，因为16个
数可以放在L1 cache里面，比读内存快很多。但如果存8位的表的话，反而会比存4位慢。 | p**l
发帖数: 703 | 4 卧槽，厉害
能设计一个hash函数确保key value一一对应就好了
【在 v******s 的大作中提到】
: 烂问题，没意思
: 先把bit分开
: int t = n&(-n) //参考binary index tree
: 再查表
: unordered_map xxx{{1, 0}{2, 1}, {4, 2} .... )
: vector bit_pos;
: while(n)
: {
: int t = n & (-n);
: n -= t;
| v******s
发帖数: 144 | | p**l
发帖数: 703 | 6 发现取37的模，既可以用一个长度37的数组创建一个查找表。
谢谢大侠还有楼上那位。
我就没想到要用查找表
这是一个工作中遇到的问题，不是面试问题。
【在 v******s 的大作中提到】
: 不查表也许也能做，不过我不清楚怎么做。
|
|
