题目链接：剑指 Offer 15. 二进制中1的个数

解题思路一：位运算

计算(n & 1) == 1，如果满足条件，那么就让返回的结果res++；然后令n无符号右移一位，直至n == 0

这里面涉及到的位运算符有:

  • &，即：按位与
  • 无符号右移>>>，无符号右移num >>> n的意思是，无论num是正数还是负数，将其右移n位后，高位补0

代码

Java

  1. public class Solution {
  2.     // you need to treat n as an unsigned value
  3.     public int hammingWeight(int n) {
  4.         int res = 0;
  5.         while(n != 0){
  6.             res += n & 1;
  7.             n = n >>> 1;
  8.         }
  9.         return res;
  10.     }
  11. }

复杂度分析

  • 时间复杂度：O(N)

其中，N 为二进制数的长度，我们需要对二进制数的每一位和 1 做与运算并让二进制数无符号右移直至二进制数为 0；所以该算法的时间复杂度为：O(N)
_

  • 空间复杂度：O(1)


我们只使用了有限的几个变量，所以该算法的额外空间复杂度为：_O(1)
_

解题思路二：巧用位运算n & (n - 1)

n & (n - 1)是位运算中非常非常重要的一种技巧，它是将二进制数n最右边的1变成0的操作

示例：n = 10101000

  1. n = 10101000
  2. n - 1 = 10100111
  3. n & (n - 1) = 10100000 // 将二进制数n最右边的那个1变成了0，其余不变

有了这个技巧，我们就可以优化我们的算法，将算法的时间复杂度提升到O(M)

其中M为二进制数n中1的个数

代码

Java

  1. public class Solution {
  2.     // you need to treat n as an unsigned value
  3.     public int hammingWeight(int n) {
  4.         int res = 0;
  5.         while(n != 0){
  6.             n = n & (n - 1);
  7.             res++;
  8.         }
  9.         return res;
  10.     }
  11. }

复杂度分析

  • 时间复杂度：O(M)


_M 为二进制数 N 中 1 的个数，相比于第一种算法，该算法的时间复杂度要优于前者。

  • 空间复杂度：O(1)


算法中只使用到了有限的几个变量，所以额外空间复杂度为：_O(1)