代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
一个快速的c#解决方案,使用预先计算的字节位计数表,并根据输入大小进行分支。
public static class BitCount
{
public static uint GetSetBitsCount(uint n)
{
var counts = BYTE_BIT_COUNTS;
return n <= 0xff ? counts[n]
: n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
: n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
: counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
}
public static readonly uint[] BYTE_BIT_COUNTS =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
}
其他回答
int bitcount(unsigned int n)
{
int count=0;
while(n)
{
count += n & 0x1u;
n >>= 1;
}
return count;
}
迭代的“计数”运行的时间与总比特数成比例。它只是循环遍历所有位,因为while条件而稍微提前终止。如果1'S或集合位是稀疏的且在最低有效位之间,则很有用。
这是一个有助于了解您的微架构的问题。我只是在gcc 4.3.3下用-O3编译的两个变量使用c++内联来计时,以消除函数调用开销,十亿次迭代,保持所有计数的运行总和,以确保编译器不删除任何重要的东西,使用rdtsc计时(精确的时钟周期)。
inline int pop2(unsigned x, unsigned y) { x = x - ((x >> 1) & 0x55555555); y = y - ((y >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); y = (y & 0x33333333) + ((y >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0F0F0F0F; y = (y + (y >> 4)) & 0x0F0F0F0F; x = x + (x >> 8); y = y + (y >> 8); x = x + (x >> 16); y = y + (y >> 16); return (x+y) & 0x000000FF; }
未经修改的黑客喜悦需要122亿周期。我的并行版本(计算的比特数是它的两倍)的运行周期为13.0千兆周期。在2.4GHz的酷睿双核上,两者总共消耗了10.5秒。在这个时钟频率下,25千兆周期= 10秒多一点,所以我相信我的计时是正确的。
这与指令依赖链有关,这对算法非常不利。通过使用一对64位寄存器,我几乎可以再次将速度提高一倍。事实上,如果我聪明一点,早点加上x+y,我就可以减少一些移位。64位版本做了一些小的调整,结果是相同的,但又增加了一倍的比特数。
对于128位SIMD寄存器,这是另一个因素,SSE指令集通常也有聪明的快捷方式。
没有理由让代码特别透明。该算法界面简单,可在多处在线引用,并能通过全面的单元测试。偶然发现它的程序员甚至可能学到一些东西。这些位操作在机器级别上是非常自然的。
好吧,我决定搁置调整后的64位版本。对于这个sizeof(unsigned long) == 8
inline int pop2(unsigned long x, unsigned long y) { x = x - ((x >> 1) & 0x5555555555555555); y = y - ((y >> 1) & 0x5555555555555555); x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333); y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333); x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F; y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F; x = x + y; x = x + (x >> 8); x = x + (x >> 16); x = x + (x >> 32); return x & 0xFF; }
这看起来是对的(不过我没有仔细测试)。现在计时结果是10.70亿周期/ 14.1亿周期。后面的数字加起来是1280亿比特,相当于这台机器运行了5.9秒。非并行版本稍微加快了一点,因为我在64位模式下运行,它更喜欢64位寄存器,而不是32位寄存器。
让我们看看这里是否有更多的OOO管道。这有点复杂,所以我实际上测试了一些。每一项单独加起来是64,所有项加起来是256。
inline int pop4(unsigned long x, unsigned long y, unsigned long u, unsigned long v) { enum { m1 = 0x5555555555555555, m2 = 0x3333333333333333, m3 = 0x0F0F0F0F0F0F0F0F, m4 = 0x000000FF000000FF }; x = x - ((x >> 1) & m1); y = y - ((y >> 1) & m1); u = u - ((u >> 1) & m1); v = v - ((v >> 1) & m1); x = (x & m2) + ((x >> 2) & m2); y = (y & m2) + ((y >> 2) & m2); u = (u & m2) + ((u >> 2) & m2); v = (v & m2) + ((v >> 2) & m2); x = x + y; u = u + v; x = (x & m3) + ((x >> 4) & m3); u = (u & m3) + ((u >> 4) & m3); x = x + u; x = x + (x >> 8); x = x + (x >> 16); x = x & m4; x = x + (x >> 32); return x & 0x000001FF; }
我兴奋了一会儿,但结果是gcc在-O3上玩内联的把戏,尽管我在一些测试中没有使用内联关键字。当我让gcc玩把戏时,对pop4()的十亿次调用需要12.56 gigacycles,但我确定它是将参数折叠为常量表达式。更实际的数字似乎是19.6gc,以实现30%的加速。我的测试循环现在看起来像这样,确保每个参数足够不同,以阻止gcc耍花招。
hitime b4 = rdtsc(); for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i) sum += pop4 (i, i^1, ~i, i|1); hitime e4 = rdtsc();
2560亿比特加起来在8.17秒内过去了。根据16位表查找的基准测试,3200万比特的计算结果为1.02秒。不能直接比较,因为另一个工作台没有给出时钟速度,但看起来我已经把64KB表版本的鼻涕打出来了,这首先是L1缓存的悲惨使用。
更新:决定做明显的和创建pop6()通过增加四个重复的行。结果是22.8gc, 3840亿比特在9.5秒内加起来。所以还有20%现在是800毫秒,320亿比特。
这就是所谓的“汉明权重”,“popcount”或“横向相加”。
一些cpu有单独的内置指令来做这件事,而另一些cpu有并行指令来处理位向量。像x86的popcnt(在支持它的cpu上)这样的指令几乎肯定对单个整数来说是最快的。其他一些架构可能有一个缓慢的指令,实现了一个微编码循环,每个周期测试一个比特(需要引用-硬件popcount通常是快速的,如果它存在的话。)
“最佳”算法实际上取决于你所使用的CPU以及你的使用模式。
Your compiler may know how to do something that's good for the specific CPU you're compiling for, e.g. C++20 std::popcount(), or C++ std::bitset<32>::count(), as a portable way to access builtin / intrinsic functions (see another answer on this question). But your compiler's choice of fallback for target CPUs that don't have hardware popcnt might not be optimal for your use-case. Or your language (e.g. C) might not expose any portable function that could use a CPU-specific popcount when there is one.
不需要(或受益于)任何硬件支持的可移植算法
如果您的CPU有一个很大的缓存,并且您在一个紧密的循环中执行大量这些操作,那么预先填充的表查找方法可以非常快。然而,它可能会因为“缓存丢失”的代价而受到影响,在这种情况下,CPU必须从主存中获取一些表。(分别查找每个字节以保持表小。)如果你想要popcount的连续范围的数字,只有低字节改变的组256个数字,这是非常好的。
如果你知道你的字节大部分是0或1,那么就有针对这些情况的有效算法,例如在循环中使用bithack清除最低的集合,直到它变成0。
我相信一个非常好的通用算法是以下,称为“并行”或“可变精度SWAR算法”。我已经在一个类似C的伪语言中表达了这一点,你可能需要调整它以适用于特定的语言(例如使用uint32_t for c++和>>> in Java):
GCC10和clang 10.0可以识别这种模式/习惯用法,并在可用时将其编译为硬件popcnt或等效指令,为您提供两全其美的服务。(https://godbolt.org/z/qGdh1dvKK)
int numberOfSetBits(uint32_t i)
{
// Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
// C or C++: use uint32_t
i = i - ((i >> 1) & 0x55555555); // add pairs of bits
i = (i & 0x33333333) + ((i >> 2) & 0x33333333); // quads
i = (i + (i >> 4)) & 0x0F0F0F0F; // groups of 8
return (i * 0x01010101) >> 24; // horizontal sum of bytes
}
对于JavaScript:强制为整数|0的性能:更改第一行为i = (i|0) - ((i >> 1) & 0x55555555);
这是所有讨论过的算法中最糟糕的行为,因此可以有效地处理您抛出的任何使用模式或值。(它的性能不依赖于普通cpu的数据,在普通cpu中,包括乘法在内的所有整数操作都是常量时间。“简单”输入不会让它变得更快,但它仍然相当不错。)
引用:
https://graphics.stanford.edu/~seander/bithacks.html https://catonmat.net/low-level-bit-hacks用于bithack基础知识,例如如何减去1翻转连续的零。 https://en.wikipedia.org/wiki/Hamming_weight http://gurmeet.net/puzzles/fast-bit-counting-routines/ http://aggregate.ee.engr.uky.edu/MAGIC/人口% 20计数% 20(% 20计数)
这个SWAR bithack如何工作:
i = i - ((i >> 1) & 0x55555555);
第一步是屏蔽的优化版本,以隔离奇数/偶数位,移动以对齐它们,并添加。这有效地在2位累加器(SWAR = SIMD Within A Register)中进行16个独立的加法。比如(i & 0x55555555) + ((i>>1) & 0x55555555)。
下一步是取这16个2位累加器中的奇/偶8个,然后再次相加,得到8个4位累加器。我…这次不可能进行优化,所以它只是在移动之前/之后进行遮罩。使用相同的0x33…两次都是常量,而不是0xccc…在为需要单独在寄存器中构造32位常量的isa编译时,在移位之前进行转换是一件好事。
(i + (i >> 4)) & 0x0F0F0F0F的最后一个移位和添加步骤将扩大为4个8位累加器。它在加后而不是加前进行掩码,因为如果设置了所有对应的4位输入位,则任何4位累加器中的最大值为4。4+4 = 8仍然适合4位,所以在I + (I >> 4)中,啃食元素之间的进位是不可能的。
到目前为止,这只是使用SWAR技术和一些聪明的优化的相当普通的SIMD。继续相同的模式2步可以扩大到2x 16位,然后1x 32位计数。但在硬件快速相乘的机器上,有一种更有效的方法:
一旦我们有足够少的“元素”,一个神奇常数的乘法可以把所有的元素加起来变成最上面的元素。在本例中是字节元素。乘法是通过左移和加法完成的,因此x * 0x01010101的乘法得到x + (x<<8) + (x<<16) + (x<<24)。我们的8位元素足够宽(并且包含足够小的计数),因此不会产生进位到前8位。
它的64位版本可以使用0x0101010101010101乘数在64位整数中处理8x 8位元素,并使用>>56提取高字节。所以它不需要任何额外的步骤,只是更大的常数。这是当硬件popcnt指令未启用时,GCC在x86系统上对__builtin_popcountll使用的方法。如果您可以为此使用内置或内在函数,那么这样做可以让编译器有机会进行特定于目标的优化。
对于更宽的向量具有完整的SIMD(例如计算整个数组)
这种逐位swar算法可以在多个向量元素中同时进行并行运算,而不是在单个整数寄存器中进行并行运算,从而在具有SIMD但没有可用popcount指令的cpu上实现加速。(例如x86-64代码必须在任何CPU上运行,而不仅仅是Nehalem或更高版本。)
然而,对popcount使用矢量指令的最佳方法通常是使用变量-shuffle并行地对每个字节每次4位进行表查找。(4位索引保存在向量寄存器中的16项表)。
在Intel cpu上,硬件64位popcnt指令的性能比SSSE3 PSHUFB位并行实现的性能好2倍,但前提是编译器的性能恰到好处。否则,上交所可能会大幅领先。较新的编译器版本意识到popcnt对Intel的错误依赖问题。
https://github.com/WojciechMula/sse-popcount state-of-the-art x86 SIMD popcount for SSSE3, AVX2, AVX512BW, AVX512VBMI, or AVX512 VPOPCNT. Using Harley-Seal across vectors to defer popcount within an element. (Also ARM NEON) Counting 1 bits (population count) on large data using AVX-512 or AVX-2 related: https://github.com/mklarqvist/positional-popcount - separate counts for each bit-position of multiple 8, 16, 32, or 64-bit integers. (Again, x86 SIMD including AVX-512 which is really good at this, with vpternlogd making Harley-Seal very good.)
如果你使用c++,另一个选择是使用模板元编程:
// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
// return the least significant bit plus the result of calling ourselves with
// .. the shifted value
return (val & 0x1) + countBits<BITS-1>(val >> 1);
}
// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
return val & 0x1;
}
用法如下:
// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )
// another byte (this returns 7)
countBits<8>( 254 )
// counting bits in a word/short (this returns 1)
countBits<16>( 256 )
当然,你可以进一步扩展这个模板来使用不同的类型(甚至是自动检测位大小),但为了清晰起见,我让它保持简单。
edit:忘了说这很好,因为它应该在任何c++编译器中工作,它基本上只是为你展开循环,如果一个常量值用于比特计数(换句话说,我很确定这是你能找到的最快的通用方法)
对于那些想要在c++ 11中为任何无符号整数类型作为consexpr函数的人(tacklelib/include/tacklelib/utility/math.hpp):
#include <stdint.h>
#include <limits>
#include <type_traits>
const constexpr uint32_t uint32_max = (std::numeric_limits<uint32_t>::max)();
namespace detail
{
template <typename T>
inline constexpr T _count_bits_0(const T & v)
{
return v - ((v >> 1) & 0x55555555);
}
template <typename T>
inline constexpr T _count_bits_1(const T & v)
{
return (v & 0x33333333) + ((v >> 2) & 0x33333333);
}
template <typename T>
inline constexpr T _count_bits_2(const T & v)
{
return (v + (v >> 4)) & 0x0F0F0F0F;
}
template <typename T>
inline constexpr T _count_bits_3(const T & v)
{
return v + (v >> 8);
}
template <typename T>
inline constexpr T _count_bits_4(const T & v)
{
return v + (v >> 16);
}
template <typename T>
inline constexpr T _count_bits_5(const T & v)
{
return v & 0x0000003F;
}
template <typename T, bool greater_than_uint32>
struct _impl
{
static inline constexpr T _count_bits_with_shift(const T & v)
{
return
detail::_count_bits_5(
detail::_count_bits_4(
detail::_count_bits_3(
detail::_count_bits_2(
detail::_count_bits_1(
detail::_count_bits_0(v)))))) + count_bits(v >> 32);
}
};
template <typename T>
struct _impl<T, false>
{
static inline constexpr T _count_bits_with_shift(const T & v)
{
return 0;
}
};
}
template <typename T>
inline constexpr T count_bits(const T & v)
{
static_assert(std::is_integral<T>::value, "type T must be an integer");
static_assert(!std::is_signed<T>::value, "type T must be not signed");
return uint32_max >= v ?
detail::_count_bits_5(
detail::_count_bits_4(
detail::_count_bits_3(
detail::_count_bits_2(
detail::_count_bits_1(
detail::_count_bits_0(v)))))) :
detail::_impl<T, sizeof(uint32_t) < sizeof(v)>::_count_bits_with_shift(v);
}
谷歌测试库中的附加测试:
#include <stdlib.h>
#include <time.h>
namespace {
template <typename T>
inline uint32_t _test_count_bits(const T & v)
{
uint32_t count = 0;
T n = v;
while (n > 0) {
if (n % 2) {
count += 1;
}
n /= 2;
}
return count;
}
}
TEST(FunctionsTest, random_count_bits_uint32_100K)
{
srand(uint_t(time(NULL)));
for (uint32_t i = 0; i < 100000; i++) {
const uint32_t r = uint32_t(rand()) + (uint32_t(rand()) << 16);
ASSERT_EQ(_test_count_bits(r), count_bits(r));
}
}
TEST(FunctionsTest, random_count_bits_uint64_100K)
{
srand(uint_t(time(NULL)));
for (uint32_t i = 0; i < 100000; i++) {
const uint64_t r = uint64_t(rand()) + (uint64_t(rand()) << 16) + (uint64_t(rand()) << 32) + (uint64_t(rand()) << 48);
ASSERT_EQ(_test_count_bits(r), count_bits(r));
}
}