剑指 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 一个个给拎出来去统计，从左到右的拎出来，或者从右到左的拎出来。

所以，此时需要思考 二进制 的数字有什么特点，能帮助我们做到把 1 一个个单独提出来。

2、规律

如果 n & 1 = 0, 则 n 的最后一位是 0 ；如果 n & 1 = 1, 则 n 的最后一位是 1。

基于这两个特点，可以统计出最后一位是否为 1，如果为 1，则更新记录统计的 1 的个数，然后将 n 右移一位，这样就能统计到原来 n 的倒数第二位，依次操作；如果为 0，则不需要更新记录统计的 1 的个数，直接将 n 右移一位。

3、匹配

当题目涉及到二进制时，思考的方向一般都是 位运算 操作。

补充： 位运算基本知识