代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
我个人使用这个:
public static int myBitCount(long L){
int count = 0;
while (L != 0) {
count++;
L ^= L & -L;
}
return count;
}
其他回答
一个简单的算法来计算设置位的数量:
int countbits(n) {
int count = 0;
while(n != 0) {
n = n & (n-1);
count++;
}
return count;
}
以11(1011)为例,尝试手动运行该算法。它应该对你有很大帮助!
32位还是32位?我只是在阅读了“破解编码面试”第4版练习5.5(第5章:位操作)后,在Java中使用了这种方法。如果最小有效位是1个增量计数,则右移该整数。
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
我认为这个比常数0x33333333的解更直观,不管它们有多快。这取决于你对“最佳算法”的定义。
这可以在O(k)中完成,其中k是设置的比特数。
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
对于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
天真的解决方案
时间复杂度为O(no。n的比特数)
int countSet(unsigned int n)
{
int res=0;
while(n!=0){
res += (n&1);
n >>= 1; // logical right shift, like C unsigned or Java >>>
}
return res;
}
Brian Kerningam的算法
时间复杂度为O(n中设置位的个数)
int countSet(unsigned int n)
{
int res=0;
while(n != 0)
{
n = (n & (n-1));
res++;
}
return res;
}
32位数字的查找表方法-在这种方法中,我们将32位数字分解为4个8位数字的块
时间复杂度为O(1)
static unsigned char table[256]; /* the table size is 256,
the number of values i&0xFF (8 bits) can have */
void initialize() //holds the number of set bits from 0 to 255
{
table[0]=0;
for(unsigned int i=1;i<256;i++)
table[i]=(i&1)+table[i>>1];
}
int countSet(unsigned int n)
{
// 0xff is hexadecimal representation of 8 set bits.
int res=table[n & 0xff];
n=n>>8;
res=res+ table[n & 0xff];
n=n>>8;
res=res+ table[n & 0xff];
n=n>>8;
res=res+ table[n & 0xff];
return res;
}