专栏首页陌无崖知识分享【go】剑指offer:3种方法寻找二进制1的个数

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

作者 | 陌无崖

转载请联系授权

题目要求

传入一个整数,求其二进制中1的个数

题目分析

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

func Total_1(data int) int {
    if data == 0 {
        return 0
    }
    if data < 0 {
        data = -data
    }
    // 将数据转换成二进制
    sum := 0
    // 商
    m := data / 2
    // 余数
    n := data % 2
    // fmt.Println(n)
    for m != 0 {
        if n ==1{
            sum += n
        }
        temp := m
        m = m / 2
        // 余数
        n = temp % 2
        // fmt.Println(n)
    }
    return sum + 1
}

对于这个题,当然对于常规思路并不是这个题的考点所在,并且上述代码中有不必要的逻辑,我们可以分析二进制中1的个数和二进制的关系,很容易分析出为二进制各个数字的之和,因此在循环中没有必要进行if判断,把if语句去掉仍然可以。代码如下

func Total_1(data int) int {
    if data == 0 {
        return 0
    }
    if data < 0 {
        data = -data
    }
    // 将数据转换成二进制
    sum := 0
    // 商
    m := data / 2
    // 余数
    n := data % 2
    // fmt.Println(n)
    for m != 0 {
        sum += n
        temp := m
        m = m / 2
        // 余数
        n = temp % 2
        // fmt.Println(n)
    }
    return sum + 1
}

但是还不够,对于上述的代码以看便知有很多重复的操作,比如开始的求商,求余,那么如何简化我们的代码呢?对于这一题我们的思路需要不停的对商进行求余,那么是否可以抓换成递归传入商呢?我们可以看如下结构:假如求9的二进制f(9),f(9)代表求9的二进制1的个数,为9的余数+f(4)…..可知如下结构,假设余数为ni

    f(9)
n1        f(4)
    n2             f(2)
               n3        f(1)
                    n4         f(0)

很明显为一个树状结构,父节点的结果为子节点的和,因此我们可以写如下递归,递归的终止条件为f(0),代码如下:

func Total_two(data int) int {
    if data == 0 {
        return 0
    }
    if data < 0 {
        data = -data
    }
    m := data / 2
    n := data % 2
    return n + Total_two(m)
}

那么有没有更好的方法呢?因为我们知道,虽然递归简单,但是却消耗内存空间,有没有一种方法利用循环,仅仅说在检测到1的时候才循环呢?我们需要了解位的操作与的概念,

计算规则:两位同时为1,结果才为1,否则为0,如:3&5即 0000 0011 & 0000 0101 = 0000 0001因此,3&5的值得1。如:0&0=0;0&1=0;1&0=0;1&1=1;

我们可以将原始二进制数字减去1,如1010——>1001,将1001和1010做与运算发现结果为1000,我们发现原始数据的最右边的1变成了0。那么我们按照这样的方法只需要不停的将1变成0即可。代码如下:

func Total_three(data int) int {
    count := 0
    if data <= 0 {
        data = -data
    }
    for data != 0 {
        data = data & (data - 1)
        count++
    }
    return count
}

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e),作者:无崖子天下无敌

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

原始发表时间:2019-12-31

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指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】15. 二进制中 1 的个数

    瑞新
  • 【剑指offer】9.二进制中1的个数

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

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

    大家好,我是程序员吴师兄,欢迎来到 图解剑指 Offer 结构化专栏,在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码,希望能帮助你即使在面...

    五分钟学算法
  • 剑指offer No.11 二进制中1的个数

    week
  • 剑指OFFER之二进制中1的个数(九度OJ1513)

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

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

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

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

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

    小白学视觉
  • 剑指Offer LeetCode 面试题15. 二进制中1的个数

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

    TrueDei
  • 【剑指offer题解】二维数组中的查找

    如果你和我一样是个算法菜鸡,那么最推荐的是先把剑指offer的题目搞明白,其次再去刷LeetCode等习题,这样对于面试突击非常有用,因为面试官最常考的算法题都...

    蛮三刀酱
  • LeetCode 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

    freesan44
  • 干了三年的程序员花了一年时间才拿下头条offer,原因竟然是这个!

    1.老板张一鸣跟我是福建老乡,龙岩市在我朋友说来就是山沟沟,能走出美团王兴和头条张一鸣让我卯足了去龙岩吃特产老鼠干的欲望。

    Java程序猿
  • 剑指Offer的学习笔记(C#篇)-- 二进制中1的个数

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

    WeiMLing
  • 从简历被拒到收割今日头条 offer ,我花了一年时间

    今天分享一篇好友的面试经验给大家,他在文中总结的 积累工具类算法 来准备大厂的算法面试小吴觉得对大家很有帮助!

    五分钟学算法
  • 从简历被拒到收割今日头条offer,我花了一年时间!

    1.老板张一鸣跟我是福建老乡,龙岩市在我朋友说来就是山沟沟,能走出美团王兴和头条张一鸣让我卯足了去龙岩吃特产老鼠干的欲望。

    Python数据科学
  • 剑指Offer - 面试题15. 二进制中1的个数(位运算)

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

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

    乔戈里

扫码关注云+社区

领取腾讯云代金券