[LeetCode]191. Number of 1 Bits | 汉明重量几种解法

题目来源：LeetCode: number-of-1-bits

问题描述：二进制串中1的个数，又被称为汉明重量

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.

方案1：

Note：从末尾开始，逐位统计1的个数；末位为1时为奇数，除2操作即为右移一位。

1
2
3
4
5
6
7
8
9
10
int hammingWeight(uint32_t n) {
  int count=0;
  while(n)
  {
    if(n%2)
      count++;
    n /= 2;
  }
  return count;
}

方案2：

Note：从末尾开始，逐位统计1的个数，多用位操作的方式

1
2
3
4
5
6
7
8
9
int hammingWeight(uint32_t n) {
  int count=0;
  while(n)
  {
    count+=n&1; 
    n>>=1;
  }
  return count;
}

方案3：

Note：利用特性n&(n-1)的结果为n去除最右侧1后的数。循环次数相较方案1、2有效减少。

1
2
3
4
5
6
7
8
9
int hammingWeight(uint32_t n) {
  int count=0;
  while(n)
  {
    n &= (n-1);
    count++;
  }
  return count;
}

方案4：

Note：维基百科中Hamming Weight的巧妙方法。

1
2
3
4
5
6
7
8
int hammingWeight(uint32_t n) {
  n = (n&0x55555555) + ((n>>1)&0x55555555);
  n = (n&0x33333333) + ((n>>2)&0x33333333);
  n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
  n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
  n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);
  return n;
}

这种方式暂时还没理解，可参考这篇文章进一步理解。