代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
我认为最快的方法——不使用查找表和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位字。
其他回答
我给出了两个算法来回答这个问题,
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)
*/
}
"最佳算法"是什么意思?短码还是长码?您的代码看起来非常优雅,并且具有恒定的执行时间。代码也很短。
但如果速度是主要因素,而不是代码大小,那么我认为以下方法可以更快:
static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
static int bitCountOfByte( int value ){
return BIT_COUNT[ value & 0xFF ];
}
static int bitCountOfInt( int value ){
return bitCountOfByte( value )
+ bitCountOfByte( value >> 8 )
+ bitCountOfByte( value >> 16 )
+ bitCountOfByte( value >> 24 );
}
我认为这不会更快的64位值,但32位值可以更快。
你可以:
while(n){
n = n & (n-1);
count++;
}
这背后的逻辑是n-1位从n的最右边的集合位倒出来。
如果n=6,即110,那么5是101,位从n的最右边的集合位倒出来。
因此,如果我们&这两个,我们将在每次迭代中使最右边的位为0,并且总是到下一个最右边的集位。因此,计数设置位。当每一位都被设置时,最糟糕的时间复杂度将是O(log n)。
在Java 8或9中只调用Integer。bitCount。
我在任何地方都没见过这种方法:
int nbits(unsigned char v) {
return ((((v - ((v >> 1) & 0x55)) * 0x1010101) & 0x30c00c03) * 0x10040041) >> 0x1c;
}
它每字节工作一次,所以对于一个32位整数,它必须被调用四次。它源于横向加法,但它使用两个32位乘法将指令数量减少到只有7条。
大多数当前的C编译器将使用SIMD (SSE2)指令优化这个函数,当请求的数量是4的倍数时,它变得非常有竞争力。它是可移植的,可以定义为宏或内联函数,并且不需要数据表。
这种方法可以扩展为一次处理16位,使用64位乘法。但是,当所有16位都被设置时,它会失败,返回0,所以它只能在0xFFFF输入值不存在时使用。由于64位操作,它也比较慢,并且没有很好地优化。