题目描述

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

法一：库函数

  • 使用 bin() 函数可以得到一个整数的二进制字符串
  • 注意二进制以“0b”开头
  • 时间复杂度 O(k)

  • 空间复杂度 O(k) 其中 k 为 n 的二进制长度

    1. class Solution(object):
    2.   def hammingWeight(self, n):
    3.       return bin(n).count("1")

    法二：逐步右移统计 1 的个数

  • java注意逻辑右移和算数右移的差异

    • 算术右移 >> ：舍弃最低位，高位用符号位填补
    • 逻辑右移 >>> ：舍弃最低位，高位用 0 填补
  • n & 1 判断末尾是否为 1；然后把n右移，直到结束
  • 时间复杂度：O(k)

  • 空间复杂度：O(1)

    1. class Solution(object):
    2.   def hammingWeight(self, n):
    3.       res = 0
    4.       while n:
    5.           res += n & 1
    6.           n >>= 1
    7.       return res
    1. class Solution {
    2. public:
    3.   int hammingWeight(uint32_t n) {
    4.       int res = 0;
    5.       while (n) {
    6.           res += n & 1;
    7.           n >>= 1;
    8.       }
    9.       return res;
    10.   }
    11. };

    法三：就涉及到 Brian Kernighan Algorithm

  • 反正我是想不到，题解里面现学的（抄的），题解总有很多骚姿势

  • n &(n - 1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果

    1. class Solution {
    2. public:
    3.   int hammingWeight(uint32_t n) {
    4.       int res = 0;
    5.       while (n) {
    6.           n = n & (n - 1);
    7.           res ++;
    8.       }
    9.       return res;
    10.   }
    11. };

    法四：还有一个终极解法（jdk源码）

  • 时间复杂度：O(logk)，k 为 int 的位数，固定为 32 位

  • 空间复杂度：O(1)
  • 巨人的肩膀：https://zhuanlan.zhihu.com/p/70950198
    1. class Solution {
    2. public:
    3.   int hammingWeight(uint32_t n) {
    4.       n = (n & 0x55555555) + ((n >> 1)  & 0x55555555);
    5.       n = (n & 0x33333333) + ((n >> 2)  & 0x33333333);
    6.       n = (n & 0x0f0f0f0f) + ((n >> 4)  & 0x0f0f0f0f);
    7.       n = (n & 0x00ff00ff) + ((n >> 8)  & 0x00ff00ff);
    8.       n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    9.       return n;
    10.   }
    11. };