1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 15 题] “二进制中1的个数”做题记录

[剑指 Offer 第 2 版第 15 题] “二进制中1的个数”做题记录

第 15 题:二进制中 1 的个数

传送门:二进制中 1 的个数牛客网 online judge 地址

输入一个 32 位整数,输出该数二进制表示中1的个数。

注意

  • 负数在计算机中用其绝对值的补码来表示。

样例1:

输入:9 输出:2 解释:9 的二进制表示是 1001,一共有 2 个 1 。

样例2:

输入:-2 输出:31 解释:-2 在计算机里会被表示成 11111111111111111111111111111110,一共有 31 个 1 。

知识点:1、什么是补码补码就是一个数与另一个数相加,是一个进制表示下很整的数;

2、正数的补码就是它自己,负数在计算机中的表示是它的补码

3、数分为:“有符号整数”与“无符号整数”。

记住:1、n & (n - 1) 把最低位的 1 变成 0

2、Python 中的二进制有陷阱,参考资料:https://www.cnblogs.com/klchang/p/8017627.html。

笔记:

liwei201910110_1.png

liwei20191019_2.png

分析:位运算的问题,看答案做出来的,记住 n & (n-1) 能够消掉最低位的 1 即可。

Python 代码1:一位一位算就可以了,注意,做 32 次就可以了。

  class Solution(object):
        def NumberOf1(self, n):
            """
            :type n: int
            :rtype: int
            """
            ans = 0
            for i in range(32):
                if n & 1:
                    ans += 1
                n = n >> 1

            return ans

Python 代码2:Python 中的数是长整型,因此一开始做的时候,要把高于 32 位的全部砍掉

  class Solution(object):
        def NumberOf1(self, n):
            """
            :type n: int
            :rtype: int
            """
            # print((-1 & (2**31-1)) >> 1)
            # print((-3) >> 1)
            n = n & (2 ** 32 - 1)
            # print(n)
            count = 0
            while n != 0:
                if n & 1 == 1:
                    count += 1
                n = n >> 1
                # print(n)
            return count

Python 代码:以下写法等价

  class Solution(object):
        def NumberOf1(self,n):
            """
            :type n: int
            :rtype: int
            """
            counter  = 0

            # Python 中的 32 位整数没有溢出这回事,所以要强行变成 32 位
            # 这一步相当于把这个数变成无符号整数,为了通过 judge 才这么做的

            n = n & 0xFFFFFFFF

            while n:
                n = n &(n-1)
                counter +=1
            return counter

C++ 写法:转成无符号数。

liwei20191016_3.png

liwei20191016_4.png


  • Java 写法

思路1:

  • 熟悉位运算是关键。
  • 负数左移的时候,最高位补 1,因此,为了避免死循环,先要把最高位变成 0。

liwei20191015_5.png

liwei20191015_6.png

Java 代码:

  public class Solution {
        public int NumberOf1(int n) {
            int count = 0;
            // 负数右移的时候,最高位补 1,因此,为了避免死循环,先要把最高位变成 0
            // 负数右移的时候,最高位补 1,因此,为了避免死循环,先要把最高位变成 0
            // 负数右移的时候,最高位补 1,因此,为了避免死循环,先要把最高位变成 0

            // 为负数的时候,将最高位的 1 变成 0
            // 即由负数变成正数,然后再计算 1 的个数
            if (n < 0) {
                n = n & Integer.MAX_VALUE;
                count++;
            }

            // 当 n 是正数的时候,计算 1 的个数
            while (n != 0) {
                count += n & 1;
                n = n >> 1;
            }
            return count;
        }
    }

思路2:

  • 可以使用 1001 作为测试用例来理解,a&(a-1) 的结果会将 a 最右边的 1 变为 0 ,直到 a = 0,还可以先将 a&1 != 0,然后右移 1 位,但不能计算负数的值。

liwei20191015_7.png

liwei20191015_8.png

liwei20191015_9.png

Java 代码:

  public class Solution2 {
        public int NumberOf1(int n) {
            int count = 0;
            while (n != 0) {
                count++;
                n = (n - 1) & n;
            }
            return count;
        }
    }

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 15 题] “二进制中1的个数”做题记录

链接:https://www.javajike.com/article/3310.html

« [剑指 Offer 第 2 版第 9-2 题] “用队列实现栈”做题记录
[剑指 Offer 第 2 版第 32_1 题] “把二叉树打印成多行”做题记录»

相关推荐

QR code