在 UInt32 中计算设置位的最快方法是什么 [英] What is the fastest way to count set bits in UInt32

问题描述

在不使用查找表的情况下，计算 UInt32 中设置位的数量(即计算 1 的数量)的最快方法是什么?有没有办法计算O(1)?

What is the fastest way to count the number of set bits (i.e. count the number of 1s) in an UInt32 without the use of a look up table? Is there a way to count in O(1)?

推荐答案

与以下内容重复:how-to-implement-bitcount-using-only-bitwise-operators或者最佳算法-计算 32 位整数中的集合位数

这个问题有很多解决方案.我使用的是:

And there are many solutions for that problem. The one I use is:

    int NumberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }

这篇关于在 UInt32 中计算设置位的最快方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！