当前位置：文江博客话题详情

以更快的方式找出变量中没有设置的位

发布于 2024-08-14 11:15:20 字数 258 浏览 2 评论 0原文

可能的重复：
最佳计数算法32 位整数中设置的位数？

找出编号。变量中的位设置更容易。但是我们怎样才能以最快的方法执行相同的操作呢？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

撩起发的微风 2024-08-21 11:15:20

Bit Twiddling Hacks 上的此页面涵盖了几种计算位数的技术设置，并讨论每个的性能。

回复收藏 0 原文

开始看清了 2024-08-21 11:15:20

位旋转黑客页面有各种建议。

回复收藏 0 原文

久夏青 2024-08-21 11:15:20

我强烈建议您阅读黑客之乐，了解有关各种形式的位操作的所有问题。特别是对于位数计数，它会根据您可能可用的指令分析多种算法。

回复收藏 0 原文

楠木可依 2024-08-21 11:15:20

如果您问这个问题，那么 gcc 上的 __builtin_popcount 可能至少与您当前正在执行的操作一样快。 __builtin_popcount 通常可以在 x86 上被打败，所以想必在其他 CPU 上也是如此，但你没有说你的 CPU 除了“嵌入式”之外是什么。影响答案。

如果您不使用 gcc，那么您需要了解如何在实际编译器和/或 CPU 上进行快速 popcount。由于显而易见的原因，不存在“计算 C 中设置位的最快方法”这样的东西。

回复收藏 0 原文

烟柳画桥 2024-08-21 11:15:20

int i, size, set;
for (i = 1, size = sizeof(int) * 8; i <= size; i++)
{
    if (value & (0 << 2 * i)) set++;    
}

int i, size, set;
for (i = 1, size = sizeof(int) * 8; i <= size; i++)
{
    if (value & (0 << 2 * i)) set++;    
}

回复收藏 0 原文

春庭雪 2024-08-21 11:15:20

对变量中设置的位进行计数称为“总体计数”，缩写为“popcount”。

不同软件算法的非常好的微基准如下：http://www.dalkescientific.com/writings/diary/archive/2008/07/05/bitslice_and_popcount.html

AMD“Barcelona”处理器具有快速固定成本指令，在 GCC 中您可以在英特尔机器上使用 __builtin_popcount

我发现循环中的 __builtin_ffs 最适合稀疏位集。

它是你不能依赖的东西；如果这对您很重要，您必须进行微基准测试。

回复收藏 0 原文

紫南 2024-08-21 11:15:20

如果变量是整数，您可以使用

   public static int BitCount(int x)
        { return ((x == 0) ? 0 : ((x < 0) ? 1 : 0) + BitCount(x <<= 1)); }

解释来计算位数：
递归，如果 number 为零，则不设置任何位，并且函数返回零
否则，它检查符号位，如果 set 存储 1，否则存储 0，
然后将整个数字向左移动一位
消除刚刚检查的符号位，
并在最右边的位加一个零，
并用新的左移值再次调用自身。

总体结果是检查从最左到最右的每一位，对于每一个集合，将该位是否已设置（如 1/0）存储在堆栈上，左移下一位到符号位位置并返回。当它最终到达最后一个位集时，该值将为零并且递归将停止。然后函数返回调用堆栈，将其存储的所有临时值相加。退货总额

If variable is an integer, you can count bits using

   public static int BitCount(int x)
        { return ((x == 0) ? 0 : ((x < 0) ? 1 : 0) + BitCount(x <<= 1)); }

Explanation:
Recursive, if number is zero, no bits are set, and function returns a zero
else, it checks the sign bit and if set stores 1 else stores a 0,
then shifts the entire number one bit to the left
eliminating the sign bit just examined,
and putting a zero in rightmost bit,
and calls itself again with new left-Shifted value.

Overall result is to examine each bit from leftmost to rightmost, and for each one set, stores on stack whether that bit was set (as 1/0), left-Shits next bit into sign bit position and resurses. When it finally gets to the last bit set , the value will be zero and recursion will stop. Function then returns up the call stack, adding up all the temp values it stored on the way down. Returns total

回复收藏 0 原文

~没有更多了~