代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
int countBits(int x)
{
int n = 0;
if (x) do n++;
while(x=x&(x-1));
return n;
}
或者:
int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }
在我最初的回答7年半之后,@PeterMortensen质疑这是否是有效的C语法。我发布了一个在线编译器的链接,显示它实际上是完全有效的语法(代码如下)。
#include <stdio.h>
int countBits(int x)
{
int n = 0;
if (x) do n++; /* Totally Normal Valid code. */
while(x=x&(x-1)); /* Nothing to see here. */
return n;
}
int main(void) {
printf("%d\n", countBits(25));
return 0;
}
输出:
3
如果你想重新写清楚,它看起来是这样的:
if (x)
{
do
{
n++;
} while(x=x&(x-1));
}
但在我看来,这太过分了。
然而,我也意识到函数可以变得更短,但可能更神秘,写为:
int countBits(int x)
{
int n = 0;
while (x) x=(n++,x&(x-1));
return n;
}
其他回答
我认为最快的方法——不使用查找表和popcount——是以下方法。它仅通过12次操作来计数设置位。
int popcount(int v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
它之所以有效,是因为你可以通过将设置位分为两半来计算总设置位的数量,计算两半设置位的数量,然后将它们相加。也被称为分而治之范式。让我们来详细谈谈。
v = v - ((v >> 1) & 0x55555555);
两位位数可以是0b00、0b01或0b10。让我们试着在2位上解决这个问题。
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
这就是所需要的:最后一列显示每两个位对中设置位的计数。如果两个比特数>= 2 (0b10),则产生0b01,否则产生0b00。
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
这句话应该很容易理解。在第一个操作之后,我们每两个比特中就有一个set位的计数,现在我们每4个比特中就有一个set位的计数。
v & 0b00110011 //masks out even two bits
(v >> 2) & 0b00110011 // masks out odd two bits
然后我们把上面的结果加起来,得到4位的集合位总数。最后一个陈述是最棘手的。
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
让我们进一步分析一下……
v + (v >> 4)
这和第二种说法很相似;我们以4为一组来计数集合位。因为我们之前的运算,我们知道每一个咬痕都有一个集合位的计数。让我们看一个例子。假设我们有字节0b01000010。这意味着第一个啃食有它的4位设置,第二个有它的2位设置。现在我们把这些小块加在一起。
v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100
它为我们提供了一个字节中set位的计数,在第二个nibble 0b01000110中,因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。
0b01000110 & 0x0F = 0b00000110
现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010,它有一个有趣的属性。如果我们的数字有四个字节,A B C D,它将产生一个新的数字,包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位,可以表示为0b00100000。
我们现在需要的是第一个字节,它是所有字节中所有set位的和,我们通过>> 24得到它。该算法是为32位字设计的,但可以很容易地修改为64位字。
def hammingWeight(n):
count = 0
while n:
if n&1:
count += 1
n >>= 1
return count
你可以这样做:
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
工作原理如下:
首先,所有的偶数位都向右移动,并与奇数位相加,以计算两组位的数量。 然后我们两人一组,然后四个人,以此类推。
public class BinaryCounter {
private int N;
public BinaryCounter(int N) {
this.N = N;
}
public static void main(String[] args) {
BinaryCounter counter=new BinaryCounter(7);
System.out.println("Number of ones is "+ counter.count());
}
public int count(){
if(N<=0) return 0;
int counter=0;
int K = 0;
do{
K = biggestPowerOfTwoSmallerThan(N);
N = N-K;
counter++;
}while (N != 0);
return counter;
}
private int biggestPowerOfTwoSmallerThan(int N) {
if(N==1) return 1;
for(int i=0;i<N;i++){
if(Math.pow(2, i) > N){
int power = i-1;
return (int) Math.pow(2, power);
}
}
return 0;
}
}
这就是所谓的“汉明权重”,“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.)