大家好,我是程序员吴师兄,欢迎来到 图解剑指 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、边界

三、动画描述

隐藏内容
本内容需权限查看
  • 普通: 5积分
  • 会员: 免费
  • 算法训练营永久会员: 免费

四、图片描述

五、参考代码

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

七、相关标签

  • 位运算
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。