专栏首页五分钟学算法剑指 Offer 15 . 二进制中 1 的个数

剑指 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)。

七、相关标签

  • 位运算

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】15. 二进制中 1 的个数

    瑞新
  • 剑指Offer - 面试题15. 二进制中1的个数(位运算)

    请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

    Michael阿明
  • 剑指Offer LeetCode 面试题15. 二进制中1的个数

    请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

    TrueDei
  • 剑指Offer-二进制中1的个数

    package Other; /** * 二进制中1的个数 * 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 */ public c...

    武培轩
  • 剑指offer:二进制中1的个数

    本来是打算次条每天更新面试题和算法刷题的,加上头条一共要三篇文章,实在更不来,而且两篇都看的人也不多,所以我就算法刷题和面试题论着更新,更新的时候多更新几道。

    帅地
  • 剑指offer--二进制中1的个数

    C++代码思路 这题有3种思路。第一种:让n与1相与后判断是否为真,若为真,计数器cnt加一并将n右移1位直至n为0。这种思路受限于n是否为正数,若n为负数...

    AI那点小事
  • 【剑指offer】9.二进制中1的个数

    二进制或运算符(or):符号为|,表示若两个二进制位都为0,则结果为0,否则为1。

    ConardLi
  • 剑指offer No.11 二进制中1的个数

    week
  • 剑指 offer 面试题精选图解 15 . 二进制中 1 的个数

    请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9转换为二进制是1001,有2位是1。因此如果输入9,该函数输出2.

    五分钟学算法
  • 剑指OFFER之二进制中1的个数(九度OJ1513)

    题目描述: 输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 输入: 输入可能包含多个测试样例。 对于每个输入文件,第一行输入一个整数T,代表测...

    用户1154259
  • 剑指Offer面试题:9.二进制中1的个数

      一个基本的思路:先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位,此时原来处于从右边数起的第二位被移到最右边了,再判断是不是1。这样每次移...

    Edison Zhou
  • 每日一题 剑指offer(二进制中1的个数)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 剑指Office-二进制中1的个数

    TrueDei
  • 剑指offer_9_二进制中1的个数

    描述:输入一个整数 判断这个整数的二进制中有多少个1,要考虑输入的是负数 所以不能把输入的数往右移动。

    用户6055494
  • 剑指Offer的学习笔记(C#篇)-- 二进制中1的个数

    新颖的解法,使得该题目运用到了二进制的位运算符。先了解一下位运算符!

    WeiMLing
  • 每天一道剑指offer-牛客网二进制中1的个数

    乔戈里
  • C#版 - 剑指offer 面试题10:二进制中1的个数 题解

    提交网址: http://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8?tpId=13&...

    Enjoy233
  • 【go】剑指offer:3种方法寻找二进制1的个数

    对于该题很容易有思路,我们将整数进行二进制的转换的过程中记录余数为1的个数即可。需要注意的是传入的负数和循环的终止条件,代码如下,因为循环的终止条件为商为0时停...

    陌无崖
  • 剑指offer——面试题10输入一个十进制整数,统计其中二进制1的个数

    /** * 题目:输入一个十进制整数,统计其中二进制1的个数 * @author 大闲人柴毛毛 */ public class CountBitOne {...

    大闲人柴毛毛

扫码关注云+社区

领取腾讯云代金券