代表数字7的8位像这样:

00000111

设置了三个比特。

确定32位整数中设置位数的算法是什么?


当前回答

这可以在O(k)中完成,其中k是设置的比特数。

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}

其他回答

Java JDK1.5

Integer.bitCount (n);

其中n是要计算1的数。

检查,

Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);

//Beginning with the value 1, rotate left 16 times
     n = 1;
         for (int i = 0; i < 16; i++) {
            n = Integer.rotateLeft(n, 1);
            System.out.println(n);
         }

Python的解决方案:

def hammingWeight(n: int) -> int:
    sums = 0
    while (n!=0):
        sums+=1
        n = n &(n-1)

    return sums

在二进制表示中,n中最不有效的1位总是对应n - 1中的0位。因此,对n和n - 1这两个数进行and运算总是将n中最不有效的1位翻转为0,并保持所有其他位相同。

有许多算法来计数设置位;但是我认为最好的一个是更快的一个! 您可以在本页查看详细信息:

Bit Twiddling Hacks

我建议这样做:

使用64位指令计数在14,24或32位字中设置的位

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

这种方法需要64位CPU和快速模除法来提高效率。第一个选项只需要3个操作;第二种选择需要10;第三种选择需要15分钟。

当你写出比特模式时,“黑客的喜悦”比特旋转变得更加清晰。

unsigned int bitCount(unsigned int x)
{
  x = ((x >> 1) & 0b01010101010101010101010101010101)
     + (x       & 0b01010101010101010101010101010101);
  x = ((x >> 2) & 0b00110011001100110011001100110011)
     + (x       & 0b00110011001100110011001100110011); 
  x = ((x >> 4) & 0b00001111000011110000111100001111)
     + (x       & 0b00001111000011110000111100001111); 
  x = ((x >> 8) & 0b00000000111111110000000011111111)
     + (x       & 0b00000000111111110000000011111111); 
  x = ((x >> 16)& 0b00000000000000001111111111111111)
     + (x       & 0b00000000000000001111111111111111); 
  return x;
}

第一步将偶数位加到奇数位上,产生每两个位的和。其他步骤将高阶数据块添加到低阶数据块,将数据块的大小一直增加一倍,直到最终计数占用整个int。

这可以在O(k)中完成,其中k是设置的比特数。

int NumberOfSetBits(int n)
{
    int count = 0;

    while (n){
        ++ count;
        n = (n - 1) & n;
    }

    return count;
}