代表数字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];
}
其他回答
我给出了两个算法来回答这个问题,
package countSetBitsInAnInteger;
import java.util.Scanner;
public class UsingLoop {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
try {
System.out.println("Enter a integer number to check for set bits in it");
int n = in.nextInt();
System.out.println("Using while loop, we get the number of set bits as: " + usingLoop(n));
System.out.println("Using Brain Kernighan's Algorithm, we get the number of set bits as: " + usingBrainKernighan(n));
System.out.println("Using ");
}
finally {
in.close();
}
}
private static int usingBrainKernighan(int n) {
int count = 0;
while(n > 0) {
n& = (n-1);
count++;
}
return count;
}
/*
Analysis:
Time complexity = O(lgn)
Space complexity = O(1)
*/
private static int usingLoop(int n) {
int count = 0;
for(int i=0; i<32; i++) {
if((n&(1 << i)) != 0)
count++;
}
return count;
}
/*
Analysis:
Time Complexity = O(32) // Maybe the complexity is O(lgn)
Space Complexity = O(1)
*/
}
你要找的函数通常被称为二进制数的“横向和”或“总体数”。Knuth在前分册1A,第11-12页中讨论了它(尽管在第2卷,4.6.3-(7)中有简要的参考)。
经典文献是Peter Wegner的文章“二进制计算机中的一种计数技术”,摘自ACM通讯,卷3(1960)第5号,第322页。他给出了两种不同的算法,一种针对“稀疏”(即1的数量很少)的数字进行了优化,另一种针对相反的情况。
有些语言以一种可以使用有效硬件支持(如果可用的话)的方式可移植地公开操作,而有些语言则希望使用一些不错的库。
例如(从语言表中):
c++有std::bitset<>::count()或c++ 20 std::popcount(T x) Java有Java .lang. integer . bitcount()(也用于Long或BigInteger) c#有system . numbers . bitoperations . popcount () Python有int.bit_count()(从3.10开始)
不过,并不是所有的编译器/库都能在HW支持可用时使用它。(值得注意的是MSVC,即使有选项使std::popcount内联为x86 popcnt,它的std::bitset::count仍然总是使用查找表。这有望在未来的版本中改变。)
当可移植语言没有这种基本的位操作时,还要考虑编译器的内置函数。以GNU C为例:
int __builtin_popcount (unsigned int x);
int __builtin_popcountll (unsigned long long x);
In the worst case (no single-instruction HW support) the compiler will generate a call to a function (which in current GCC uses a shift/and bit-hack like this answer, at least for x86). In the best case the compiler will emit a cpu instruction to do the job. (Just like a * or / operator - GCC will use a hardware multiply or divide instruction if available, otherwise will call a libgcc helper function.) Or even better, if the operand is a compile-time constant after inlining, it can do constant-propagation to get a compile-time-constant popcount result.
GCC内置甚至可以跨多个平台工作。Popcount几乎已经成为x86架构的主流,所以现在开始使用内置是有意义的,这样你就可以重新编译,让它内联硬件指令时,你编译-mpopcnt或包括(例如https://godbolt.org/z/Ma5e5a)。其他架构已经有popcount很多年了,但在x86领域,仍然有一些古老的Core 2和类似的老式AMD cpu在使用。
在x86上,你可以告诉编译器它可以通过-mpopcnt(也可以通过-msse4.2暗示)假设支持popcnt指令。参见GCC x86选项。-march=nehalem -mtune=skylake(或-march=任何您希望您的代码假设和调优的CPU)可能是一个不错的选择。在较旧的CPU上运行生成的二进制文件将导致非法指令错误。
要为构建它们的机器优化二进制文件,请使用-march=native(与gcc、clang或ICC一起使用)。
MSVC为x86的popcnt指令提供了一个内在的特性,但与gcc不同的是,它实际上是硬件指令的一个内在特性,需要硬件支持。
使用std::bitset<>::count()代替内置的
理论上,任何知道如何有效地为目标CPU进行popcount的编译器都应该通过ISO c++ std::bitset<>来公开该功能。实际上,对于某些目标cpu,在某些情况下使用bit-hack AND/shift/ADD可能会更好。
For target architectures where hardware popcount is an optional extension (like x86), not all compilers have a std::bitset that takes advantage of it when available. For example, MSVC has no way to enable popcnt support at compile time, and it's std::bitset<>::count always uses a table lookup, even with /Ox /arch:AVX (which implies SSE4.2, which in turn implies the popcnt feature.) (Update: see below; that does get MSVC's C++20 std::popcount to use x86 popcnt, but still not its bitset<>::count. MSVC could fix that by updating their standard library headers to use std::popcount when available.)
但是,至少您得到了可以在任何地方工作的可移植的东西,并且使用带有正确目标选项的gcc/clang,您可以获得支持它的体系结构的硬件popcount。
#include <bitset>
#include <limits>
#include <type_traits>
template<typename T>
//static inline // static if you want to compile with -mpopcnt in one compilation unit but not others
typename std::enable_if<std::is_integral<T>::value, unsigned >::type
popcount(T x)
{
static_assert(std::numeric_limits<T>::radix == 2, "non-binary type");
// sizeof(x)*CHAR_BIT
constexpr int bitwidth = std::numeric_limits<T>::digits + std::numeric_limits<T>::is_signed;
// std::bitset constructor was only unsigned long before C++11. Beware if porting to C++03
static_assert(bitwidth <= std::numeric_limits<unsigned long long>::digits, "arg too wide for std::bitset() constructor");
typedef typename std::make_unsigned<T>::type UT; // probably not needed, bitset width chops after sign-extension
std::bitset<bitwidth> bs( static_cast<UT>(x) );
return bs.count();
}
参见Godbolt编译器资源管理器上gcc、clang、icc和MSVC中的asm。
x86-64 gcc -O3 -std=gnu++11 -mpopcnt输出:
unsigned test_short(short a) { return popcount(a); }
movzx eax, di # note zero-extension, not sign-extension
popcnt rax, rax
ret
unsigned test_int(int a) { return popcount(a); }
mov eax, edi
popcnt rax, rax # unnecessary 64-bit operand size
ret
unsigned test_u64(unsigned long long a) { return popcount(a); }
xor eax, eax # gcc avoids false dependencies for Intel CPUs
popcnt rax, rdi
ret
PowerPC64 gcc -O3 -std=gnu++11发出(对于int arg版本):
rldicl 3,3,0,32 # zero-extend from 32 to 64-bit
popcntd 3,3 # popcount
blr
这个源代码不是x86特定的,也不是gnu特定的,只是在gcc/clang/icc下编译得很好,至少在针对x86(包括x86-64)时是这样。
还要注意,对于没有单指令popcount的体系结构,gcc的回退是逐字节表查找。例如,这对ARM来说就不是什么好事。
c++ 20有std::popcount(T)
不幸的是,当前libstdc++头文件用特殊情况定义了它,if(x==0) return 0;在开始时,clang在编译x86时不会优化:
#include <bit>
int bar(unsigned x) {
return std::popcount(x);
}
clang 11.0.1 -O3 -std=gnu++20 -march=nehalem (https://godbolt.org/z/arMe5a)
# clang 11
bar(unsigned int): # @bar(unsigned int)
popcnt eax, edi
cmove eax, edi # redundant: if popcnt result is 0, return the original 0 instead of the popcnt-generated 0...
ret
但是GCC编译得很好:
# gcc 10
xor eax, eax # break false dependency on Intel SnB-family before Ice Lake.
popcnt eax, edi
ret
即使是MSVC也能很好地使用它,只要你使用-arch:AVX或更高版本(并使用-std:c++latest启用c++ 20)。https://godbolt.org/z/7K4Gef
int bar(unsigned int) PROC ; bar, COMDAT
popcnt eax, ecx
ret 0
int bar(unsigned int) ENDP ; bar
下面是PHP中的一些东西(所有PHP整数都是32位符号,因此是31位):
function bits_population($nInteger)
{
$nPop=0;
while($nInteger)
{
$nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
$nPop++;
}
return $nPop;
}
下面是示例代码,可能很有用。
private static final int[] bitCountArr = new int[]{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};
private static final int firstByteFF = 255;
public static final int getCountOfSetBits(int value){
int count = 0;
for(int i=0;i<4;i++){
if(value == 0) break;
count += bitCountArr[value & firstByteFF];
value >>>= 8;
}
return count;
}