各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 57 天。今天力扣上的每日一题是「191. 位1的个数」。

解题思路

今天的题目又可以重拳出击。

一、库函数

在 Python 语言中，使用 bin() 函数可以得到一个整数的二进制字符串。比如 bin(666) 会得到：

  1. >>> bin(666)
  2. '0b1010011010'

得到二进制字符串，统计字符串中 "1" 的次数即可。

需要注意的是，二进制字符串是以 "0b" 开头，所以如果题目要问的是二进制中 0 的个数，需要注意答案是 bin(n).count("0") - 1。

  1. class Solution(object):
  2.     def hammingWeight(self, n):
  3.         return bin(n).count("1")
  • 时间复杂度：$O(k)$，k 为 n 的二进制长度。
  • 空间复杂度：$O(k)$，k 为 n 的二进制长度。

二、右移 32 次

如果除去库函数之外，我们最容易想到的办法，肯定还是直观地统计二进制中每一位是否包含 1 。

做法是：

  • 使用 n & 1 得到二进制末尾是否为 1；
  • 把 n 右移 1 位，直至结束。

于是我们可以写出以下的代码：

  1. class Solution:
  2.     def hammingWeight(self, n: int) -> int:
  3.         count = 0
  4.         while n:
  5.             count += 1
  6.             n &= n - 1
  7.         return count
  1. public class Solution {
  2.     // you need to treat n as an unsigned value
  3.     public int hammingWeight(int n) {
  4.         int count = 0;
  5.         for (int i = 0; i < 32; ++i) {
  6.             count += n & 1;
  7.             n >>= 1;
  8.         }
  9.         return count;
  10.     }
  11. }

值得一提的时候，在 Java 中，以下代码会 超时。这就不得不讲一讲 Java 中的 算术右移 和 逻辑右移 。

  • 算术右移 >> ：舍弃最低位，高位用符号位填补；
  • 逻辑右移 >>> ：舍弃最低位，高位用 0 填补。

那么对于负数而言，其二进制最高位是 1，如果使用算术右移，那么高位填补的仍然是 1。也就是 n 永远不会为 0。所以下面的代码会超时。

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

在 Java 中需要使用逻辑右移，即 >>> ，while 的判断条件才能是 n != 0 。代码如下：

  1. public class Solution {
  2.     // you need to treat n as an unsigned value
  3.     public int hammingWeight(int n) {
  4.         int count = 0;
  5.         while (n != 0) {
  6.             count += n & 1;
  7.             n >>>= 1;
  8.         }
  9.         return count;
  10.     }
  11. }
  • 时间复杂度：$O(k)$，k 为 n 的二进制长度。
  • 空间复杂度：$O(1)$。

三、消除二进制末尾的 1

有个更为神奇的做法，那就是 n & (n - 1) ，这个代码可以把 n 的二进制中，最后一个出现的 1 改写成 0。

下面的这个图，说明了 n & (n - 1)这个操作的原理。我们发现只要每次执行这个操作，就会消除掉 n 的二进制中 最后一个出现的 1。

因此执行 n & (n - 1) 使得 n 变成 0 的操作次数，就是 n 的二进制中 1 的个数。
image.png

  1. class Solution(object):
  2.     def hammingWeight(self, n):
  3.         res = 0
  4.         while n:
  5.             res += 1
  6.             n &= n - 1
  7.         return res
  • 时间复杂度：$O(k)$，k 为 n 的二进制长度。
  • 空间复杂度：$O(1)$。

    刷题心得

今天这个题非常经典，特别是 n & (n - 1) 的技巧可以消除二进制中最后一个 1，虽然该技巧在刷题中用到的不多，但是还是推荐掌握。位运算就是这么神奇。

参考资料：图源，leetcode 的官方题解。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！