一、题目

请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

点击查看原题
难度级别： 简单

二、 思路

1）按位运算

由于给定的是32位int型数据，需要计算二进制位中所有1的个数，可以去位移并判断每一位是否为1，进行计数

2）数学方法

采用n &= n-1的方式消去n中存在的1，原理（举例）如下：

n = 0000 0000 0000 1100 n-1 = 0000 0000 0000 1011 n & (n-1) = ``0000 0000 0000 1000

因为n-1会消去最低位的1，进行与运算，就消去了最低位的1

三、代码

1）按位运算

  1. public class Solution {
  2.     public int hammingWeight(int n) {
  3.         int ans = 0;
  4.         while (n != 0) {
  5.             if ((n & 1) == 1) {
  6.                 ans++;
  7.             }
  8.             n = n >>> 1;
  9.         }
  10.         return ans;
  11.     }
  12. }

n为32，时间复杂度为O(n)，空间复杂度为O(1)

2）数学方法

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

n为32，时间复杂度为O(logn)，空间复杂度为O(1)