文档章节

剑指Offer(Java版):二进制中的1的个数

一贱书生
 一贱书生
发布于 2016/07/18 11:30
字数 1599
阅读 11
收藏 0

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

1、可能引起死循环的解法

这是一道很基本的考察二进制和位运算的面试题。题目不是很难,面试官 提出问题之后,我们很快形成一个基本的思路:先判断证书二进制表示中最右边一位是不是1.接着把输入的证书右移一位,此时原来处于从右边树起的第二位被移 到最后一位,再判断是不是1.这样没移动一位,知道整个整数变成0为止。现在的问题变成怎么判断一个整数的最右边是不是1了。这很简单,只要把整数和1做 位与运算看结果是不是0就知道了。1除了最右边的一位之外所有的位都是0.基于这个思路,我们很快写出这样的代码:

package cglib;

public class List1
{  
    public static int numberOf1(int num) {  
        int count = 0;

        while(num!=0){

        if((num&1)!=0)

        count++;

        num = num>>1;

        }

        return count;
    }  
 
    public static void main(String[] args) {  
        
        System.out.println(numberOf1(9));  
        System.out.println(numberOf1(-9));
}
}

只输出了2

负数死循环

面试官看了 代码后可能会问:把证书右移一位和把整数除以2在数学上是等价的,那上面的代码中可以把右移换成除以2吗?答案是否定的。因为除法的效率比移位运算要低很多,在实际编程中应尽可能地用移位运算代替乘除法。

面试官会问第二个问题就是:上面的函数如果输入一个负数,比如 0x80000000,运行的时候会发生什么情况呢?把负数0x80000000右移一位的时候,并不是简单地把最高位的1移到第二位变成 0x40000000,而是0xC0000000.这是因为移位前是个负数,仍然保证移位是个负数,因此移位后的最高位会设为1.如果一直做右移位运算, 最终这个数字会编程0xFFFFFFFF而陷入死循环。

2、常规解法:

为了避免死循环,我们可以不右移输入的数字n.首先把n和1做与运算,判断n的最低位是不是1.接着把1左移一位得到2,再和n做与运算,就能判断n的次低位是不是1。。。。这样反复左移,每次都能判断n的其中一位是不是1.基于这种思路,我们可以写出这样的代码:

package cglib;

public class List1
{  
    public static int numberOf1(int num) {  
        int count = 0;

        int flag= 1;

        while(flag!=0){

        if((num&flag)!=0)

        count++;

        flag =flag <<1;

        }

        return count;
    }  
 
    public static void main(String[] args) {  
        
        System.out.println(numberOf1(9));  
        System.out.println(numberOf1(-9));
}
}

输出:

2
31

 

这个解法中循环的次数等于二进制中的位数,32位的整数需要循环32次,下面我们再介绍一个算法,整数中有几个1就只循环几次。

 

3、能给面试官带来惊喜的算法。

我们的分析就是:把一个整数减去1,再和原整数做与运算,会把该整数最右边的一个1变成0.那么一个整数的二进制表示中有多少个1,就可以进行多少次运算。基于这种思路,我们可以写出这样的代码:

package cglib;

public class List1
{  
    public static int numberOf1(int num) {  
        int count = 0;  
        while (num != 0) {  
            count++;
            System.out.println("与前:num="+num);//1001
            num = num & (num - 1);//00001001&00001000=00001000,00001000&0000111=00000000
            System.out.println("与后num="+num);
            System.out.println("count="+count);
 
        }  
        return count;  
    }  
 
    public static void main(String[] args) {  
        
        System.out.println(numberOf1(9));  
        System.out.println(numberOf1(-9));
}
}

输出:

与前:num=9
与后num=8
count=1
与前:num=8
与后num=0
count=2
2
与前:num=-9
与后num=-10
count=1
与前:num=-10
与后num=-12
count=2
与前:num=-12
与后num=-16
count=3
与前:num=-16
与后num=-32
count=4
与前:num=-32
与后num=-64
count=5
与前:num=-64
与后num=-128
count=6
与前:num=-128
与后num=-256
count=7
与前:num=-256
与后num=-512
count=8
与前:num=-512
与后num=-1024
count=9
与前:num=-1024
与后num=-2048
count=10
与前:num=-2048
与后num=-4096
count=11
与前:num=-4096
与后num=-8192
count=12
与前:num=-8192
与后num=-16384
count=13
与前:num=-16384
与后num=-32768
count=14
与前:num=-32768
与后num=-65536
count=15
与前:num=-65536
与后num=-131072
count=16
与前:num=-131072
与后num=-262144
count=17
与前:num=-262144
与后num=-524288
count=18
与前:num=-524288
与后num=-1048576
count=19
与前:num=-1048576
与后num=-2097152
count=20
与前:num=-2097152
与后num=-4194304
count=21
与前:num=-4194304
与后num=-8388608
count=22
与前:num=-8388608
与后num=-16777216
count=23
与前:num=-16777216
与后num=-33554432
count=24
与前:num=-33554432
与后num=-67108864
count=25
与前:num=-67108864
与后num=-134217728
count=26
与前:num=-134217728
与后num=-268435456
count=27
与前:num=-268435456
与后num=-536870912
count=28
与前:num=-536870912
与后num=-1073741824
count=29
与前:num=-1073741824
与后num=-2147483648
count=30
与前:num=-2147483648
与后num=0
count=31
31

扩展1:用一条语句判断一个整数是不是2的整数次方

将2的幂次方写成二进制形式后,很容易就会发现有一个特点:二进制中只有一个1,并且1后面跟了n个0; 因此问题可以转化为判断1后面是否跟了n个0就可以了。

如果将这个数减去1后会发现,仅有的那个1会变为0,而原来的那n个0会变为1;因此将原来的数与去减去1后的数字进行与运算后会发现为零。

最快速的方法:

 

(number & number - 1) == 0

扩展2:

输 入两个整数m和n,计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010,13的二进制表示为1101,需要改变1010中 的3位才能得到1101 。 我们可以分为两步解决这个问题:第一步求这两个数的异或,第二步统计异或结果中1的位数。

  1. int GetCount(int N,int M)  
  2. {  
  3.     int value=N^M;//先将两个数异或  //0111=7,0110=6
  4.     int count=0;  
  5.     while(value)  
  6.     {  
  7.         count++;  
  8.         value=(value&(value-1));//求异或后1的个数  ,0111& 0110 =0110=6;//0101=5,0100=4,
  9.     }  
  10.     return count;  

© 著作权归作者所有

一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
【剑指offer纪念版】--10 进制1的个数

题目 题目:请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。例如把9表示成二进制是1001,有2位是1。因此如果输入9,该函数输出2。 解题思路   把一个整数减去1,再和原整数做...

细节探索者
01/19
0
0
剑指offer 11二进制中1的个数

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。 java版本: public class Solution { } js版本:思路是当输入的值不是0的时候,至少有一位是1。先count++,然后解释一下n...

无敌小阿没
2018/08/14
0
0
面试:用 Java 实现一个 Singleton 模式

面试系列更新后,终于迎来了我们的第一期,我们也将贴近《剑指 Offer》的题目给大家带来 Java 的讲解,个人bogo还是非常推荐《剑指 Offer》作为面试必刷的书籍的,这不,再一次把这本书分享给...

nanchen2251
2018/07/03
0
0
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JWT学习总结

官方 https://jwt.io 英文原版 https://www.ietf.org/rfc/rfc7519.txt 或 https://tools.ietf.org/html/rfc7519 中文翻译 https://www.jianshu.com/p/10f5161dd9df 1. 概述 JSON Web Token(......

冷基
58分钟前
3
0
AOP的学习(1)

AOP 理解AOP编程思想(面向方法、面向切面) spring AOP的概念 方面 -- 功能 目标 -- 原有方法 通知 -- 对原有方法增强的方法 连接点 -- 可以用来连接通知的地方(方法) 切入点 -- 将用来插入...

太猪-YJ
今天
4
0
一张图看懂亮度、明度、光度、光亮度、明亮度

亮度、明度、光亮度,Luminance和Brightness、lightness其实都是一个意思,只是起名字太难了。 提出一个颜色模型后,由于明度的取值与别人的不同,为了表示区别所以就另想一个词而已。 因此在...

linsk1998
昨天
8
0
Python应用:python链表示例

前言 python链表应用源码示例,需要用到python os模块方法、函数和类的应用。 首先,先简单的来了解下什么是链表?链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是...

python小白1
昨天
4
0
Source Insight加载源码

Source Insight是一个图形化的源代码查看工具(当然也可以作为编译工具)。如果一个项目的源代码较多,此工具可以很方便地查找到源代码自建的依赖关系。 1.创建工程 下图为Snort源代码的文件...

天王盖地虎626
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部