作者简介:一名大一在校生
个人主页:月亮嚼成星~
个人WeChat:yx1552029968
系列专栏:每日一道LeetCode
每日一句: 决定一个人成就的,不是靠天,也不是靠运气,而是坚持和付出,是不停地做,重复的做,用心去做,当你真的努力了付出了,你会发现自己潜力无限!
目录
编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为汉明重量)。
示例 1:
- 输入:00000000000000000000000000001011
- 输出:3
- 解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。
示例 2:
- 输入:00000000000000000000000010000000
- 输出:1
- 解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。
示例 3:
- 输入:11111111111111111111111111111101
- 输出:31
- 解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。
提示:这道题涉及到了二进制位运算和移位运算的知识,不知道的铁汁们可以看一下博主的这一篇文章,浅浅的介绍了相关知识,帮助我们来做题:【Java SE]位运算和移位运算注意事项
方法一:暴力移位求解
为了记录1的位数,我们需要设置一个计数器count并将其初始化为0;为了得出一个位置是否为1,要用按位与(&)1来进行操作,如果是1,结果就是1,不是1,结果为0。这只是一个位置的比较,考虑到有32位,所以我们运用位运算来实现每一位与1进行比较,循环后即可得到1的数。 为了便于理解,画了个第一次比较的图,后面的比较方法一样。
这道题当然会有更多优秀的解法,随着思路的开阔,我们将会想到更多好的解法!
代码执行:
- public class Solution {
- // you need to treat n as an unsigned value
- public int hammingWeight(int n) {
- int count=0;//计数器
- for(int i=31;i>=0;i--){
- if(((n>>i)&1)==1){
- count++;
- }
- }
- return count;
-
- }
- }
- 复杂度分析:时间复杂度
O(k)
,k=32。空间复杂度为O(1)
执行结果:
方法2:优化循环的过程
思路:巧用二进制公式x&(x-1)表示去掉二进制中最右边的第一个1,加速循环过程
代码执行:
- public class Solution {
- public int hammingWeight(int n) {
- int ret = 0;
- while (n != 0) {
- n &= n - 1;
- ret++;
- }
- return ret;
- }
- }
运行结果:
复杂度分析:时间复杂度为O(k),k为二进制中1的个数,最坏的情况下所有位都是1。空间复杂度是O(1)
每天都来刷一道LeetCode是多么幸福的一件事,各位,共勉!!