代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
我发现了一个在数组中使用SIMD指令(SSSE3和AVX2)的位计数实现。它的性能比使用__popcnt64内禀函数要好2-2.5倍。
SSSE3版:
#include <smmintrin.h>
#include <stdint.h>
const __m128i Z = _mm_set1_epi8(0x0);
const __m128i F = _mm_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m128i T = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m128i _sum = _mm128_setzero_si128();
for (size_t i = 0; i < size; i += 16)
{
//load 16-byte vector
__m128i _src = _mm_loadu_si128((__m128i*)(src + i));
//get low 4 bit for every byte in vector
__m128i lo = _mm_and_si128(_src, F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m128i hi = _mm_and_si128(_mm_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm_add_epi64(_sum, _mm_sad_epu8(Z, _mm_shuffle_epi8(T, hi)));
}
uint64_t sum[2];
_mm_storeu_si128((__m128i*)sum, _sum);
return sum[0] + sum[1];
}
AVX2 版本:
#include <immintrin.h>
#include <stdint.h>
const __m256i Z = _mm256_set1_epi8(0x0);
const __m256i F = _mm256_set1_epi8(0xF);
//Vector with pre-calculated bit count:
const __m256i T = _mm256_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
uint64_t BitCount(const uint8_t * src, size_t size)
{
__m256i _sum = _mm256_setzero_si256();
for (size_t i = 0; i < size; i += 32)
{
//load 32-byte vector
__m256i _src = _mm256_loadu_si256((__m256i*)(src + i));
//get low 4 bit for every byte in vector
__m256i lo = _mm256_and_si256(_src, F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, lo)));
//get high 4 bit for every byte in vector
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(_src, 4), F);
//sum precalculated value from T
_sum = _mm256_add_epi64(_sum, _mm256_sad_epu8(Z, _mm256_shuffle_epi8(T, hi)));
}
uint64_t sum[4];
_mm256_storeu_si256((__m256i*)sum, _sum);
return sum[0] + sum[1] + sum[2] + sum[3];
}
其他回答
对于JavaScript,你可以使用一个查找表来计算一个32位值的设置位的数量(这段代码可以很容易地翻译成C语言)。此外,添加了8位和16位版本,以供通过网络搜索查找的人使用。
const COUNT_BITS_TABLE = makeLookupTable() function makeLookupTable() { const table = new Uint8Array(256) for (let i = 0; i < 256; i++) { table[i] = (i & 1) + table[(i / 2) | 0]; } return table } function countOneBits32(n) { return COUNT_BITS_TABLE[n & 0xff] + COUNT_BITS_TABLE[(n >> 8) & 0xff] + COUNT_BITS_TABLE[(n >> 16) & 0xff] + COUNT_BITS_TABLE[(n >> 24) & 0xff]; } function countOneBits16(n) { return COUNT_BITS_TABLE[n & 0xff] + COUNT_BITS_TABLE[(n >> 8) & 0xff] } function countOneBits8(n) { return COUNT_BITS_TABLE[n & 0xff] } console.log('countOneBits32', countOneBits32(0b10101010000000001010101000000000)) console.log('countOneBits32', countOneBits32(0b10101011110000001010101000000000)) console.log('countOneBits16', countOneBits16(0b1010101000000000)) console.log('countOneBits8', countOneBits8(0b10000010))
将整数转换为二进制字符串并计数。
PHP解决方案:
substr_count(decbin($integer), '1');
// How about the following:
public int CountBits(int value)
{
int count = 0;
while (value > 0)
{
if (value & 1)
count++;
value <<= 1;
}
return count;
}
当你写出比特模式时,“黑客的喜悦”比特旋转变得更加清晰。
unsigned int bitCount(unsigned int x)
{
x = ((x >> 1) & 0b01010101010101010101010101010101)
+ (x & 0b01010101010101010101010101010101);
x = ((x >> 2) & 0b00110011001100110011001100110011)
+ (x & 0b00110011001100110011001100110011);
x = ((x >> 4) & 0b00001111000011110000111100001111)
+ (x & 0b00001111000011110000111100001111);
x = ((x >> 8) & 0b00000000111111110000000011111111)
+ (x & 0b00000000111111110000000011111111);
x = ((x >> 16)& 0b00000000000000001111111111111111)
+ (x & 0b00000000000000001111111111111111);
return x;
}
第一步将偶数位加到奇数位上,产生每两个位的和。其他步骤将高阶数据块添加到低阶数据块,将数据块的大小一直增加一倍,直到最终计数占用整个int。
对于232查找表和逐个遍历每个位之间的折中方法:
int bitcount(unsigned int num){
int count = 0;
static int nibblebits[] =
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
for(; num != 0; num >>= 4)
count += nibblebits[num & 0x0f];
return count;
}
从http://ctips.pbwiki.com/CountBits