I found the following code to count the number of 1-bits in binary representation for given integer. Can anyone explain how it works? And how are the bit masks chosen for such task? Thanks.
我找到以下代码来计算给定整数的二进制表示中的1位数。谁能解释它是如何工作的?如何为这样的任务选择位掩码?谢谢。
int count_one(int x)
{
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
return x;
}
4 个解决方案
#1
8
This algorithm uses x as both the source of the computation and as memory. First, think about what the bitmasks are:
该算法使用x作为计算源和存储器。首先,考虑一下bitmasks是什么:
0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111
Let's go with an 8 bit example: a = 01101010
让我们看一个8位的例子:a = 01101010
a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101
If we add these two together, we get the bit count of each two bit pair. This result is at most 0x10, as the mask has only one bit set for each addition.
如果我们将这两者加在一起,我们得到每两位对的位数。此结果最多为0x10,因为掩码每次添加仅设置一个位。
Now, we use the 0x33 mask, remember each consecutive 2 bits contain the result from the first operation. With this mask, we mask out consecutive 4 bits and add them. This result is at most 0x100. This goes on with the other masks, until we have the result in x.
现在,我们使用0x33掩码,记住每个连续的2位包含第一次操作的结果。使用此掩码,我们屏蔽连续的4位并添加它们。此结果最多为0x100。这继续使用其他掩码,直到我们得到x的结果。
Try it on paper, it will be pretty clear after a few steps.
在纸上试一下,经过几个步骤后会很清楚。
#2
4
It's a divide and conquer approach. Note that the first line will give you the sum on subsequent pairs, next the sum on subsequent quadruples,... and finally the number of bits.
这是一种分而治之的方法。请注意,第一行将为后续对提供总和,接下来是后续四元组的总和,...以及最后的位数。
Example (16 bit so consider your code without the last line)
示例(16位因此请考虑没有最后一行的代码)
1011001111000110
In the fist line we take & with even bits and odd bits shifted by one. Then we add.
在第一行中,我们采用&偶数位和奇数位移一位。然后我们补充说。
For even bits:
对于偶数位:
num: 10 11 00 11 11 00 01 10
mask: 01 01 01 01 01 01 01 01
res: 00 01 00 01 01 00 01 00
For odd bits:
对于奇数位:
num>>1: 01 01 10 01 11 10 00 11
mask: 01 01 01 01 01 01 01 01
res: 01 01 00 01 01 00 00 01
We add those results and get sums in subsequent pairs
我们添加这些结果并在后续对中获得总和
01 10 00 10 10 00 01 01
We repeat the same with following masks and corresponding shifts
我们用以下面具和相应的班次重复相同的操作
2nd: 0011 0011 0011 0011
3rd: 0000 1111 0000 1111
4th: 0000 0000 1111 1111
And we get:
我们得到:
2nd: 0011 0010 0010 0010 // 3 set in the first four, 2 in other quadrupels
3rd: 0000 0101 0000 0100 // 5 bits set in the first eight, 4 in the rest
4th: 0000 0000 0000 1001 // 9 bits in total
#3
2
To make this easier to explain, let me suppose an integer is 4 bits long and each bit is represent as 1,2,3,4. In order to get the number of 1-bits, you can first get the sum of 1 and 2 and the sum of 3 and 4 and then add these sums up.
为了使这更容易解释,让我假设一个整数是4位长,每个位表示为1,2,3,4。为了获得1位的数量,您可以首先得到1和2的总和以及3和4的总和,然后将这些总和相加。
x & (0x5) will eliminate 1 and 3, and x & (0xa) will eliminate 2 and 4. x & (0x5) + (x & (0xa) >> 1) will use 1 2 bits to store the sum of 1 and 2 and use 3 4 bits to store the sum of 3 and 4. x & (0x5) + (x & (0xa) >> 1) is same as x & (0x5) + (x >> 1) & (0x5).
x&(0x5)将消除1和3,x&(0xa)将消除2和4. x&(0x5)+(x&(0xa)>> 1)将使用1 2位来存储1的总和和2并使用3 4位来存储3和4之和.x&(0x5)+(x&(0xa)>> 1)与x&(0x5)+(x >> 1)&(0x5)相同)。
Now we have the sums of 1 2 and 3 4 all stored in x, we can get the result after we add them up. Same as above, x & (0x3) will get the sum of 3 4 and x & (0x12) will get the sum of 1 2. x & (0x3) + (x & (0x12)) >> 2 will get the final result. x & (0x3) + (x & (0x12)) >> 2 is same as x & (0x3) + (x >> 2) & (0x3).
现在我们将1 2和3 4的总和全部存储在x中,我们可以在添加它们之后得到结果。与上面相同,x&(0x3)将获得3 4的总和,x&(0x12)将得到1的总和.x&(0x3)+(x&(0x12))>> 2将获得最终结果。 x&(0x3)+(x&(0x12))>> 2与x&(0x3)+(x >> 2)&(0x3)相同。
So you can see what happen inside. In your case, the first line you can get the sum of 1 2 and 3 4 and 5 6 and go on. And in the second line you get the sum of 1 2 3 4 and 5 6 7 8 and go on. So by doing this 5 times, you get the number of all 32 bits.
所以你可以看到里面发生了什么。在你的情况下,第一行你可以得到1 2和3 4和5 6的总和,然后继续。在第二行,你得到1 2 3 4和5 6 7 8的总和,然后继续。所以通过这样做5次,你得到所有32位的数量。
#4
1
The first line treats the integer as an array of 16 2-bit integers, the result of the expression is 0 if 0 bits in the 2-bit pair were set, 1 if 1 bit in the 2-bit pair was set (01 bin or 10 bin), and 2 if both bits of the 2 bit pair were set. This is because we consider the lower of every two bits of x, and the lower of every two bits of x shifted right by one; adding them together. We know no carries will occur outside of the 2-bit pairs because our summands are limited to 0 or 1. The result is then stored back into x.
第一行将整数视为16个2位整数的数组,如果设置了2位对中的0位,则表达式的结果为0;如果设置了2位对中的1位,则表达式为1(01 bin或者10 bin),如果设置了2位对的两个位,则为2。这是因为我们考虑x的每两位中的较低位,并且x的每两位中的较低位右移一位;将它们加在一起。我们知道在2位对之外不会发生进位,因为我们的求和被限制为0或1.然后将结果存储回x。
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
x =(x&(0x55555555))+((x >> 1)&(0x55555555));
The next line does the same thing, this time treating every 2-bits as a separate integer, storing their sum in every 4-bits the two summands used to occupy. After this operation the integer essentially becomes an array of 8 4-bit integers. Before the operation each summand is either 0, 1, or 2 (decimal) because it corresponds to the counts from the last line. Because of this we know each sum will be no greater than 4. Since each 4-bit int has a maximum value of 15 (decimal), we know this will also not overflow. As above, the result is stored back into x.
下一行做同样的事情,这次将每2位作为一个单独的整数处理,将它们的总和存储在用于占用的两个加数的每4位中。在此操作之后,整数基本上变为8个4位整数的数组。在操作之前,每个summand是0,1或2(十进制),因为它对应于最后一行的计数。因此我们知道每个总和不会大于4.因为每个4位int的最大值为15(十进制),我们知道这也不会溢出。如上所述,结果存储回x。
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
x =(x&(0x33333333))+((x >> 2)&(0x33333333));
We do the same as above, this time suming every pair of 4-bits into every set of 8 bits.
我们也是如上所述,这次将每对4位加到每组8位中。
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
x =(x&(0x0f0f0f0f))+((x >> 4)&(0x0f0f0f0f));
We then sum ever pair of 8-bits into every pair of 16 bits (the upper and lower half of x).
然后,我们将每对16位(x的上半部分和下半部分)中的一对8位相加。
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
x =(x&(0x00ff00ff))+((x >> 8)&(0x00ff00ff));
We now sum the upper and lower half of x, and we are left with a 32-bit value equal to the number of bits set in the value of x.
我们现在将x的上半部分和下半部分相加,并且我们留下32位值,该值等于x值中设置的位数。
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
x =(x&(0x0000ffff))+((x >> 16)&(0x0000ffff));
The key here is that each step does an inplace pairwise count of bits until we are left with the total bit count in the 32-bit integer it self.
这里的关键是每一步都进行一个就位的成对位计数,直到我们留下32位整数的总位数。
#1
8
This algorithm uses x as both the source of the computation and as memory. First, think about what the bitmasks are:
该算法使用x作为计算源和存储器。首先,考虑一下bitmasks是什么:
0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111
Let's go with an 8 bit example: a = 01101010
让我们看一个8位的例子:a = 01101010
a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101
If we add these two together, we get the bit count of each two bit pair. This result is at most 0x10, as the mask has only one bit set for each addition.
如果我们将这两者加在一起,我们得到每两位对的位数。此结果最多为0x10,因为掩码每次添加仅设置一个位。
Now, we use the 0x33 mask, remember each consecutive 2 bits contain the result from the first operation. With this mask, we mask out consecutive 4 bits and add them. This result is at most 0x100. This goes on with the other masks, until we have the result in x.
现在,我们使用0x33掩码,记住每个连续的2位包含第一次操作的结果。使用此掩码,我们屏蔽连续的4位并添加它们。此结果最多为0x100。这继续使用其他掩码,直到我们得到x的结果。
Try it on paper, it will be pretty clear after a few steps.
在纸上试一下,经过几个步骤后会很清楚。
#2
4
It's a divide and conquer approach. Note that the first line will give you the sum on subsequent pairs, next the sum on subsequent quadruples,... and finally the number of bits.
这是一种分而治之的方法。请注意,第一行将为后续对提供总和,接下来是后续四元组的总和,...以及最后的位数。
Example (16 bit so consider your code without the last line)
示例(16位因此请考虑没有最后一行的代码)
1011001111000110
In the fist line we take & with even bits and odd bits shifted by one. Then we add.
在第一行中,我们采用&偶数位和奇数位移一位。然后我们补充说。
For even bits:
对于偶数位:
num: 10 11 00 11 11 00 01 10
mask: 01 01 01 01 01 01 01 01
res: 00 01 00 01 01 00 01 00
For odd bits:
对于奇数位:
num>>1: 01 01 10 01 11 10 00 11
mask: 01 01 01 01 01 01 01 01
res: 01 01 00 01 01 00 00 01
We add those results and get sums in subsequent pairs
我们添加这些结果并在后续对中获得总和
01 10 00 10 10 00 01 01
We repeat the same with following masks and corresponding shifts
我们用以下面具和相应的班次重复相同的操作
2nd: 0011 0011 0011 0011
3rd: 0000 1111 0000 1111
4th: 0000 0000 1111 1111
And we get:
我们得到:
2nd: 0011 0010 0010 0010 // 3 set in the first four, 2 in other quadrupels
3rd: 0000 0101 0000 0100 // 5 bits set in the first eight, 4 in the rest
4th: 0000 0000 0000 1001 // 9 bits in total
#3
2
To make this easier to explain, let me suppose an integer is 4 bits long and each bit is represent as 1,2,3,4. In order to get the number of 1-bits, you can first get the sum of 1 and 2 and the sum of 3 and 4 and then add these sums up.
为了使这更容易解释,让我假设一个整数是4位长,每个位表示为1,2,3,4。为了获得1位的数量,您可以首先得到1和2的总和以及3和4的总和,然后将这些总和相加。
x & (0x5) will eliminate 1 and 3, and x & (0xa) will eliminate 2 and 4. x & (0x5) + (x & (0xa) >> 1) will use 1 2 bits to store the sum of 1 and 2 and use 3 4 bits to store the sum of 3 and 4. x & (0x5) + (x & (0xa) >> 1) is same as x & (0x5) + (x >> 1) & (0x5).
x&(0x5)将消除1和3,x&(0xa)将消除2和4. x&(0x5)+(x&(0xa)>> 1)将使用1 2位来存储1的总和和2并使用3 4位来存储3和4之和.x&(0x5)+(x&(0xa)>> 1)与x&(0x5)+(x >> 1)&(0x5)相同)。
Now we have the sums of 1 2 and 3 4 all stored in x, we can get the result after we add them up. Same as above, x & (0x3) will get the sum of 3 4 and x & (0x12) will get the sum of 1 2. x & (0x3) + (x & (0x12)) >> 2 will get the final result. x & (0x3) + (x & (0x12)) >> 2 is same as x & (0x3) + (x >> 2) & (0x3).
现在我们将1 2和3 4的总和全部存储在x中,我们可以在添加它们之后得到结果。与上面相同,x&(0x3)将获得3 4的总和,x&(0x12)将得到1的总和.x&(0x3)+(x&(0x12))>> 2将获得最终结果。 x&(0x3)+(x&(0x12))>> 2与x&(0x3)+(x >> 2)&(0x3)相同。
So you can see what happen inside. In your case, the first line you can get the sum of 1 2 and 3 4 and 5 6 and go on. And in the second line you get the sum of 1 2 3 4 and 5 6 7 8 and go on. So by doing this 5 times, you get the number of all 32 bits.
所以你可以看到里面发生了什么。在你的情况下,第一行你可以得到1 2和3 4和5 6的总和,然后继续。在第二行,你得到1 2 3 4和5 6 7 8的总和,然后继续。所以通过这样做5次,你得到所有32位的数量。
#4
1
The first line treats the integer as an array of 16 2-bit integers, the result of the expression is 0 if 0 bits in the 2-bit pair were set, 1 if 1 bit in the 2-bit pair was set (01 bin or 10 bin), and 2 if both bits of the 2 bit pair were set. This is because we consider the lower of every two bits of x, and the lower of every two bits of x shifted right by one; adding them together. We know no carries will occur outside of the 2-bit pairs because our summands are limited to 0 or 1. The result is then stored back into x.
第一行将整数视为16个2位整数的数组,如果设置了2位对中的0位,则表达式的结果为0;如果设置了2位对中的1位,则表达式为1(01 bin或者10 bin),如果设置了2位对的两个位,则为2。这是因为我们考虑x的每两位中的较低位,并且x的每两位中的较低位右移一位;将它们加在一起。我们知道在2位对之外不会发生进位,因为我们的求和被限制为0或1.然后将结果存储回x。
x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
x =(x&(0x55555555))+((x >> 1)&(0x55555555));
The next line does the same thing, this time treating every 2-bits as a separate integer, storing their sum in every 4-bits the two summands used to occupy. After this operation the integer essentially becomes an array of 8 4-bit integers. Before the operation each summand is either 0, 1, or 2 (decimal) because it corresponds to the counts from the last line. Because of this we know each sum will be no greater than 4. Since each 4-bit int has a maximum value of 15 (decimal), we know this will also not overflow. As above, the result is stored back into x.
下一行做同样的事情,这次将每2位作为一个单独的整数处理,将它们的总和存储在用于占用的两个加数的每4位中。在此操作之后,整数基本上变为8个4位整数的数组。在操作之前,每个summand是0,1或2(十进制),因为它对应于最后一行的计数。因此我们知道每个总和不会大于4.因为每个4位int的最大值为15(十进制),我们知道这也不会溢出。如上所述,结果存储回x。
x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
x =(x&(0x33333333))+((x >> 2)&(0x33333333));
We do the same as above, this time suming every pair of 4-bits into every set of 8 bits.
我们也是如上所述,这次将每对4位加到每组8位中。
x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
x =(x&(0x0f0f0f0f))+((x >> 4)&(0x0f0f0f0f));
We then sum ever pair of 8-bits into every pair of 16 bits (the upper and lower half of x).
然后,我们将每对16位(x的上半部分和下半部分)中的一对8位相加。
x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
x =(x&(0x00ff00ff))+((x >> 8)&(0x00ff00ff));
We now sum the upper and lower half of x, and we are left with a 32-bit value equal to the number of bits set in the value of x.
我们现在将x的上半部分和下半部分相加,并且我们留下32位值,该值等于x值中设置的位数。
x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
x =(x&(0x0000ffff))+((x >> 16)&(0x0000ffff));
The key here is that each step does an inplace pairwise count of bits until we are left with the total bit count in the 32-bit integer it self.
这里的关键是每一步都进行一个就位的成对位计数,直到我们留下32位整数的总位数。