二进制中1的个数

• 🏠解法一、位数检查
• 🏠解法二、右移统计
• 🏘️解法三、巧用

题目描述： 💦

👉题目链接👈

🏠解法一、位数检查

首先我们先了解一下与运算

若 n & 1 = 0，则 n 二进制 最右一位 为0 ；
若 n & 1 = 1，则 n 二进制 最右一位 为1 。

思路分析： 💫

一个朴素的做法，对 int 的每一位进行检查，并统计 1 的个数。

代码展示： 👇

public class Solution {public int hammingWeight(int n) {int ans = 0;for (int i = 0; i < 32; i++) {ans += ((n >> i) & 1);}return ans;}
}

以上算法实现的复杂度分析：

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

🏠解法二、右移统计

思路分析： 💫

1.判断 n 最右一位是否为 1 ，根据结果计数。
2.将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用无符号右移操作）

代码展示： 👇

public class Solution {public int hammingWeight(int n) {int res = 0;     //初始化数量统计变量 res = 0while(n != 0) {   //循环逐位判断：当 n = 0 时跳出res += n & 1;   //若n & 1 = 1 ，则统计数 resres 加一n >>>= 1;   //Java 中无符号右移为 ">>>" }return res;}
}

🏘️解法三、巧用

经过解法一和解法二我们又可以发现一个更简单的方法

思路分析： 💫

(n−1) 解析： 二进制数字 n 最右边的 1 变成 0 ，此 1 右边的 0 都变成 1 。
n & (n - 1)解析： 二进制数字 n 最右边的 1 变成 0 ，其余不变。
所以我们可以巧用n & (n−1)

代码展示： 👇

public class Solution {public int hammingWeight(int n) {int res = 0;     //初始化数量统计变量 reswhile(n != 0) {    res++;      //统计变量加 1n &= n - 1;    //消去数字 n 最右边的 1}return res;}
}

以上算法实现的复杂度分析：

• 时间复杂度是： O(M))，n&(n−1) 操作仅有减法和与运算，占用 O(1)；设 M 为二进制数字 n 中 1 的个数，则需循环 M 次（每轮消去一个 1 ），占用 O(M)。
• 空间复杂度是 ： O(1)，变量 res使用常数大小额外空间。

相关文章：
上一篇：【剑指offer】之《斐波那契数列》
下一篇：【剑指offer】之《在排序数组中查找数字》

🌈我的感受：

  如果对操作符的运算理解的不错的话这道题难度应该也不大，我这三种方法其实也只算一种方法不断优化而来，还有几种方法我看了一下没整明白，等我学会补上。加油，如果你选择开始刷题就要选择坚持下去，给你打气~

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！