学弟学妹们，看完这篇文章你还不会数「二进制中 1 的个数」?

矫情吗；* 2023-01-20 05:59 32阅读 0赞

学弟学妹们好，我是帅吴，欢迎来到 **图解剑指 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_.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的个数.008][1_.008 1]

![二进制中1的个数.010][1_.010]

![二进制中1的个数.011][1_.011]

![二进制中1的个数.012][1_.012]

![二进制中1的个数.013][1_.013]

![二进制中1的个数.014][1_.014]

![二进制中1的个数.015][1_.015]

![二进制中1的个数.016][1_.016]

![二进制中1的个数.017][1_.017]

![二进制中1的个数.018][1_.018]

![二进制中1的个数.019][1_.019]

![二进制中1的个数.020][1_.020]

![二进制中1的个数.021][1_.021]

![二进制中1的个数.022][1_.022]

![二进制中1的个数.023][1_.023]

![二进制中1的个数.024][1_.024]

![二进制中1的个数.025][1_.025]

![二进制中1的个数.026][1_.026]

![二进制中1的个数.027][1_.027]

![二进制中1的个数.028][1_.028]

![二进制中1的个数.029][1_.029]

#### 3、匹配 ####

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

> 补充：**位运算基本知识**

<table> 
 <thead> 
  <tr> 
   <th>符号</th> 
   <th>描述</th> 
   <th>示例</th> 
   <th>运算规则</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>&amp;</td> 
   <td>与</td> 
   <td>A &amp; B</td> 
   <td>A 和 B 都为 1 时，结果为 1</td> 
  </tr> 
  <tr> 
   <td>|</td> 
   <td>或</td> 
   <td>A | B</td> 
   <td>A 和 B 都为 0 时，结果为 0</td> 
  </tr> 
  <tr> 
   <td>^</td> 
   <td>异或</td> 
   <td>A ^ B</td> 
   <td>A 和 B 相同为 0 ，相异为 1</td> 
  </tr> 
  <tr> 
   <td>~</td> 
   <td>取反</td> 
   <td>~A</td> 
   <td>0 变 1 ，1 变 0</td> 
  </tr> 
  <tr> 
   <td>&lt;&lt;</td> 
   <td>左移</td> 
   <td>A&lt;&lt;</td> 
   <td>全部左移若干位，高位丢弃，低位补 0</td> 
  </tr> 
  <tr> 
   <td>&gt;&gt;</td> 
   <td>右移</td> 
   <td>A&gt;&gt;</td> 
   <td>全部右移若干位，对无符号数，高位补 0 ，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补 0（逻辑右移）</td> 
  </tr> 
 </tbody> 
</table>

#### 4、边界 ####

无

### 三、动画描述 ###

https://www.algomooc.com

### 四、图片描述 ###

无

### 五、参考代码 ###

// 登录 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)。

### 七、相关标签 ###

*  位运算

[1_.002]: /images/20221021/c7cc4a8576f64337bbeb13cb19bf0658.png
[1_.008]: /images/20221021/0f7f20c907b74cc59812aa90f1fd5cb9.png
[1_.008 1]: /images/20221021/07240acac9554f72b845f2291fe32a42.png
[1_.010]: /images/20221021/d0a0023cd861424f92df18ef72273775.png
[1_.011]: /images/20221021/1c1dc8666d144700a2c5ab7cea19b320.png
[1_.012]: /images/20221021/d465130574c64a5b894c746eaa052a6c.png
[1_.013]: /images/20221021/92b58eda49db4f3e845e1de06686d9a2.png
[1_.014]: /images/20221021/a534262e89c34a04ab87ee58db4ff905.png
[1_.015]: /images/20221021/29eb668c49184acd9642278da2aa80c2.png
[1_.016]: /images/20221021/e2d8d414ea3548ddb63ad4fd2586bf04.png
[1_.017]: /images/20221021/025f46394a6e43b4be1e0fa548205563.png
[1_.018]: /images/20221021/6c1def724cd3497b99290fe03b672871.png
[1_.019]: /images/20221021/65f1dbd0c7c4477bae5f9173c1dd1c14.png
[1_.020]: /images/20221021/50b8dfe49a0e492f9ae6c467ae347395.png
[1_.021]: /images/20221021/22400bcffc8945c7b25b5d1836bb2aff.png
[1_.022]: /images/20221021/8b77c719db704ae6841f07f4c4f75674.png
[1_.023]: /images/20221021/1ce3aa7cff1b49aab49b6d0d83ea2dd9.png
[1_.024]: /images/20221021/1564034b28904998a7dad0e80a351987.png
[1_.025]: /images/20221021/bea219b757e1448289531dc42f72b008.png
[1_.026]: /images/20221021/91215f115e454938ad0e28f546f18628.png
[1_.027]: /images/20221021/0699d858339242df88077e38ca6c403a.png
[1_.028]: /images/20221021/d9972b8129bd497cad0b0a3d20367819.png
[1_.029]: /images/20221021/4834fb08c5a449cda31e5e635641417d.png