代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
我给出了两个算法来回答这个问题,
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位值可以更快。
#!/user/local/bin/perl
$c=0x11BBBBAB;
$count=0;
$m=0x00000001;
for($i=0;$i<32;$i++)
{
$f=$c & $m;
if($f == 1)
{
$count++;
}
$c=$c >> 1;
}
printf("%d",$count);
ive done it through a perl script. the number taken is $c=0x11BBBBAB
B=3 1s
A=2 1s
so in total
1+1+3+3+3+2+3+3=19
对于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
为什么不迭代地除以2呢?
count = 0 while n > 0 if (n % 2) == 1 count += 1 n /= 2
我同意这不是最快的,但是“最好”这个词有点含糊不清。我认为“最好”应该有一个清晰的元素
对于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))