死磕算法系列文章
“Leetcode : https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_12_hammingWeight/Solution.java
“题目描述:编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 '1' 的个数(也被称为 汉明重量)。
这题还是挺有意思的
提示:
-3
。示例 1:
输入:n = 11 (控制台输入 00000000000000000000000000001011)
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。
示例 2:
输入:n = 128 (控制台输入 00000000000000000000000010000000)
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。
示例 3:
输入:n = 4294967293 (控制台输入 11111111111111111111111111111101,部分语言中 n = -3)
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。
提示: 输入必须是长度为 32
的 二进制串 。
根据 与运算 定义,设二进制数字 nn ,则有:
根据以上特点,考虑以下 循环判断 :
算法流程:
复杂度分析:
package com.nateshao.sword_offer.topic_12_hammingWeight;
/**
* @date Created by 邵桐杰 on 2021/11/20 12:03
* @微信公众号 程序员千羽
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description: 二进制中1的个数
*/
public class Solution {
public static void main(String[] args) {
int hammingWeight = hammingWeight(11);
System.out.println("hammingWeight = " + hammingWeight);
}
public static int hammingWeight(int n) {
int res = 0;
while (n != 0) {
res += n & 1;
n >>>= 1;
}
return res;
}
}
----hammingWeight = 3
算法流程:
res += 1
: 统计变量加 1 ;n &= n - 1
: 消去数字 n最右边的 1 。复杂度分析:
代码:
public class Solution {
public static int hammingWeight2(int n) {
int res = 0;
while (n != 0) {
res++;
n &= n - 1;
}
return res;
}
}
参考链接:https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/solution/mian-shi-ti-15-er-jin-zhi-zhong-1de-ge-shu-wei-yun
革命尚未成功,同志仍需努力,冲冲冲