剑指 Offer 15 . 二进制中 1 的个数
大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题15. 二进制中1的个数。
题目汇总链接：https://www.algomooc.com/hi-offer
一、题目描述
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1、模拟
我们统计一下二进制串 110101110 中有多少个 1，第一个想法就是从左到右一个个的数。
二进制中1的个数.002
但是由于于上述的数字是二进制的形式，因此无法做到像遍历数组或者链表那样统计，合理的思考就是怎么样做到把进制中的 1 一个个给拎出来去统计，从左到右的拎出来，或者从右到左的拎出来。
所以，此时需要思考二进制的数字有什么特点，能帮助我们做到把 1 一个个单独提出来。
2、规律
如果 n & 1 = 0, 则 n 的最后一位是 0 ；如果 n & 1 = 1, 则 n 的最后一位是 1。
基于这两个特点，可以统计出最后一位是否为 1，如果为 1，则更新记录统计的 1 的个数，然后将 n 右移一位，这样就能统计到原来 n 的倒数第二位，依次操作；如果为 0，则不需要更新记录统计的 1 的个数，直接将 n 右移一位。
二进制中1的个数.008
二进制中1的个数.008
二进制中1的个数.010
二进制中1的个数.011
二进制中1的个数.012
二进制中1的个数.013
二进制中1的个数.014
二进制中1的个数.015
二进制中1的个数.016
二进制中1的个数.017
二进制中1的个数.018
二进制中1的个数.019
二进制中1的个数.020
二进制中1的个数.021
二进制中1的个数.022
二进制中1的个数.023
二进制中1的个数.024
二进制中1的个数.025
二进制中1的个数.026
二进制中1的个数.027
二进制中1的个数.028
二进制中1的个数.029
3、匹配
当题目涉及到二进制时，思考的方向一般都是位运算操作。
补充：位运算基本知识
符号 | 描述 | 示例 | 运算规则 |
|---|---|---|---|
& | 与 | A & B | A 和 B 都为 1 时，结果为 1 |
| | 或 | A | B | A 和 B 都为 0 时，结果为 0 |
^ | 异或 | A ^ B | A 和 B 相同为 0 ，相异为 1 |
~ | 取反 | ~A | 0 变 1 ，1 变 0 |
<< | 左移 | A<< | 全部左移若干位，高位丢弃，低位补 0 |
>> | 右移 | A>> | 全部右移若干位，对无符号数，高位补 0 ，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补 0（逻辑右移） |
4、边界
无
三、动画描述
四、图片描述
无
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
public class Solution {
public int hammingWeight(int n) {
// 用来保存统计到的结果
int res = 0;
// 不断的右移 n，直到为 0
while(n != 0){
// 统计结果
res = res + (n & 1);
// 无符号右移 1 位
n = n >>> 1;
}
return res;
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O(log2n)。
空间复杂度
空间复杂度为 O(1)。
七、相关标签
- 位运算