仅使用按位运算计算设置的位数
可能的重复：
最佳计数算法32 位整数中设置的位数？
仅使用 ! 〜& ^ | + << >>>运算符，我需要计算 32 位整数中设置的位数，同时仅直接访问 8 位。所以只有 0xaa 而不是
0xaaaa 0x07 = 3 和 0x05 = 2
我也只能使用最多 40 个运算符。
现在我的解决方案使用 90 并且是：
int countBitsSet(int x)
{
int count = 0;
int mask = 0x01 // 00000001
count = (x & mask);
count += (x >> 1) & mask;
count += (x >> 2) & mask;
.
.
.
count += (x >> 31) & mask;
return count;
}
有谁知道有什么方法可以将此步骤减少一半吗？我正在考虑找到一种方法来并行执行或同时计算 4 位，但我不知道如何实现。其他人已经在 25 个运算符中做到了，所以我知道有一种方法。有什么想法吗？
Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?
Using only ! ~ & ^ | + << >> operators, I need to count the number of bits set in a 32 bit integer while only accessing directly 8 bits. So only 0xaa not 0xaaaa
Ex. 0x07 = 3 and 0x05 = 2
I also can only use a max of 40 operators.
Right now my solution uses 90 and is:
int countBitsSet(int x)
{
int count = 0;
int mask = 0x01 // 00000001
count = (x & mask);
count += (x >> 1) & mask;
count += (x >> 2) & mask;
.
.
.
count += (x >> 31) & mask;
return count;
}
Does anyone know of a way to reduce this step by half? I was thinking of finding a way to do it in parallel or something and count 4 bits at once but I cant figure out how. Other people have done it in 25 operators so I know there is a way. Any ideas?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
1）你计算出错误的结果；缺少 31 的移位。 2）你应该使用for循环。 3）搜索一下位计数算法会给你一堆链接。
1) You compute the wrong result; the shift of 31 is missing. 2) You should have used a for loop. 3) Searching a bit for bit counting algorithms would have given you a bunch of links.