代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
为什么不迭代地除以2呢?
count = 0 while n > 0 if (n % 2) == 1 count += 1 n /= 2
我同意这不是最快的,但是“最好”这个词有点含糊不清。我认为“最好”应该有一个清晰的元素
其他回答
这里有一个到目前为止还没有提到的解决方案,使用位字段。下面的程序使用4种不同的方法对100000000个16位整数数组中的设置位进行计数。计时结果在括号中给出(在MacOSX上,使用gcc -O3):
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 100000000
typedef struct {
unsigned char bit0 : 1;
unsigned char bit1 : 1;
unsigned char bit2 : 1;
unsigned char bit3 : 1;
unsigned char bit4 : 1;
unsigned char bit5 : 1;
unsigned char bit6 : 1;
unsigned char bit7 : 1;
} bits;
unsigned char sum_bits(const unsigned char x) {
const bits *b = (const bits*) &x;
return b->bit0 + b->bit1 + b->bit2 + b->bit3 \
+ b->bit4 + b->bit5 + b->bit6 + b->bit7;
}
int NumberOfSetBits(int i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
#define out(s) \
printf("bits set: %lu\nbits counted: %lu\n", 8*LENGTH*sizeof(short)*3/4, s);
int main(int argc, char **argv) {
unsigned long i, s;
unsigned short *x = malloc(LENGTH*sizeof(short));
unsigned char lut[65536], *p;
unsigned short *ps;
int *pi;
/* set 3/4 of the bits */
for (i=0; i<LENGTH; ++i)
x[i] = 0xFFF0;
/* sum_bits (1.772s) */
for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=sum_bits(*p++));
out(s);
/* NumberOfSetBits (0.404s) */
for (i=LENGTH*sizeof(short)/sizeof(int), pi=(int*)x, s=0; i--; s+=NumberOfSetBits(*pi++));
out(s);
/* populate lookup table */
for (i=0, p=(unsigned char*) &i; i<sizeof(lut); ++i)
lut[i] = sum_bits(p[0]) + sum_bits(p[1]);
/* 256-bytes lookup table (0.317s) */
for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=lut[*p++]);
out(s);
/* 65536-bytes lookup table (0.250s) */
for (i=LENGTH, ps=x, s=0; i--; s+=lut[*ps++]);
out(s);
free(x);
return 0;
}
虽然位域版本非常可读,但计时结果显示它比NumberOfSetBits()慢了4倍以上。基于查找表的实现仍然要快得多,特别是对于一个65 kB的表。
对于那些想要在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));
}
}
如果您恰好使用Java,则内置方法Integer。bitCount会这样做。
你可以这样做:
int countSetBits(int n)
{
n=((n&0xAAAAAAAA)>>1) + (n&0x55555555);
n=((n&0xCCCCCCCC)>>2) + (n&0x33333333);
n=((n&0xF0F0F0F0)>>4) + (n&0x0F0F0F0F);
n=((n&0xFF00FF00)>>8) + (n&0x00FF00FF);
return n;
}
int main()
{
int n=10;
printf("Number of set bits: %d",countSetBits(n));
return 0;
}
海王: http://ideone.com/JhwcX
工作原理如下:
首先,所有的偶数位都向右移动,并与奇数位相加,以计算两组位的数量。 然后我们两人一组,然后四个人,以此类推。
你可以:
while(n){
n = n & (n-1);
count++;
}
这背后的逻辑是n-1位从n的最右边的集合位倒出来。
如果n=6,即110,那么5是101,位从n的最右边的集合位倒出来。
因此,如果我们&这两个,我们将在每次迭代中使最右边的位为0,并且总是到下一个最右边的集位。因此,计数设置位。当每一位都被设置时,最糟糕的时间复杂度将是O(log n)。