题目链接：Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.
这道题的要求是计算一个32位整数的各个位中1的数目。
这个1的数目又被称之为汉明重量（Hamming weight）
-
按位处理
其实就是每次取出一位，然后统计其中1的数目。
时间复杂度：O(n)（n为位数）
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
class Solution
{
public:
int hammingWeight(uint32_t n)
{
int res = 0;
for(int i = 0; i < 32; ++ i)
res += n >> i & 1;
return res;
}
};
-
n&(n-1)
有这么一种事实，即n&(n-1)会削去最右端的1。减1操作将最右边的位从0变到1，从1变到0，与操作将会移除最右端的1。如果最初n有m个1，那么经过m次这样的迭代运算，n将减到0。
时间复杂度：O(m)（m为1的个数）
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution
{
public:
int hammingWeight(uint32_t n)
{
int res = 0;
while(n != 0)
{
++ res;
n &= n - 1;
}
return res;
}
};
-
树状相加
思路就是：
- 将每2位中1的数量放到这2位
- 将每4位中1的数量放到这4位
- 将每8位中1的数量放到这8位
- 将每16位中1的数量放到这16位
- 将每32位中1的数量放到这32位
得出最后1的数量。
时间复杂度：O(logn)（n为位数）
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
// This is a naive implementation, shown for comparison, and to help in understanding the better functions.
// It uses 24 arithmetic operations (shift, add, and).
int hammingWeight(uint32_t n)
{
n = (n & 0x55555555) + (n >> 1 & 0x55555555); // put count of each 2 bits into those 2 bits
n = (n & 0x33333333) + (n >> 2 & 0x33333333); // put count of each 4 bits into those 4 bits
n = (n & 0x0F0F0F0F) + (n >> 4 & 0x0F0F0F0F); // put count of each 8 bits into those 8 bits
n = (n & 0x00FF00FF) + (n >> 8 & 0x00FF00FF); // put count of each 16 bits into those 16 bits
n = (n & 0x0000FFFF) + (n >> 16 & 0x0000FFFF); // put count of each 32 bits into those 32 bits
return n;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
// This uses fewer arithmetic operations than any other known implementation on machines with slow multiplication.
// It uses 17 arithmetic operations.
int hammingWeight(uint32_t n)
{
n -= (n >> 1) & 0x55555555; // put count of each 2 bits into those 2 bits
n = (n & 0x33333333) + (n >> 2 & 0x33333333); // put count of each 4 bits into those 4 bits
n = (n + (n >> 4)) & 0x0F0F0F0F; // put count of each 8 bits into those 8 bits
n += n >> 8; // put count of each 16 bits into those 8 bits
n += n >> 16; // put count of each 32 bits into those 8 bits
return n & 0xFF;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution
{
public:
// This uses fewer arithmetic operations than any other known implementation on machines with fast multiplication.
// It uses 12 arithmetic operations, one of which is a multiply.
int hammingWeight(uint32_t n)
{
n -= (n >> 1) & 0x55555555; // put count of each 2 bits into those 2 bits
n = (n & 0x33333333) + (n >> 2 & 0x33333333); // put count of each 4 bits into those 4 bits
n = (n + (n >> 4)) & 0x0F0F0F0F; // put count of each 8 bits into those 8 bits
return n * 0x01010101 >> 24; // returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24)
}
};