【题15 二进制中1的个数】Java实现

快来打我* 2022-03-27 07:12 92阅读 0赞

**位运算**

> 位运算时把数字用二进制表示之后，对每一位上0或者1的运算。

**二进制：**  
指数字的每一位都是0或者1.  
二进制种有五种运算：与、或、异或、左移和右移  
![在这里插入图片描述][20190112154454198.png]  
**左移运算符m << n：**  
表示把m左移n位。左移n位的时候，最左边的n位将被丢弃。同时在最右边补上n个0.比如  
![在这里插入图片描述][20190112154543766.png]  
**右移运算符m >> n：**  
表示把m右移n位。右移n位的时候，最右边的n位将被丢弃。  
如果数字是一个无符号的数值，则用0填补最左边的n位。  
如果数字是一个有符号的数值，则用数字的符号位填补最左边的n位。  
（有符号的类型，1表示负数，0表示整数。右移时负数最左边补充1，正数补充0）  
也就是说  
如果数字原先是一个正数，则右移之后在最左边补n个0；  
如果数字原先是一个负数，则右移之后在最左边补n个1；  
![在这里插入图片描述][20190112154627570.png]  
**【题15 二进制中1的个数】**  
**【题目】**  
请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。  
**例如：**  
把9表示成二进制是1001，有2位是1.因此，如果输入9，则该函数输出2.

**可能引起死循环的解法：**  
**基本思路：**  
(1)先判断整数二进制表示中最右边一位是不是1；  
(2)接着把输入的整数右移一位，此时原来处于从右边起的第二位被移到最右边了，再判断是不是1.  
(3)这样每次移动一位，直到整个整数变成0位置。  
**问题变成了：如何判断一个整数的最右边是不是1.**  
只要把整数和1做位与运算看结果是不是0就知道了。  
如果一个整数与1做与运算的结果是1，则表示该整数最右边一位是1，否则是0.  
**问题1：可以把右移运算换成除以2么？**  
回答：不可以，因为除法效率比移位运算要低得多。在实际编程中，应尽可能地用移位运算符代替乘除法。  
**问题2：上面的函数如果输入一个负数。比如，0x80000000，则运行的时候会发生什么情况？**  
回答：当把负数0x80000000右移一位的时候，并不是把最简单地最高位的1移到第二位变成0x40000000，而是0xC0000000。这时因为移位前是负数，仍然要保证移位后是一个负数因此移位后的最高位会设为1。如果一直做右移运算，那么最终这个数字就会变成0xF0000000而陷入死循环。

**常规解法：**  
为避免死循环，不右移输入数字n，  
(1)把n和1做与运算，判断n的最低位是不是为1。  
(2)把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1……  
(3)这样反复左移，每次都能判断n的其中一位是不是1.  
**在这个解法中，循环次数等于整数二进制的位数，32位的整数需要循环32次。**

**带来惊喜的解法**  
**整数中有几个1就只需要循环几次**  
分析把一个整数减去1的情况。

*  如果一个整数不等于0，那么该整数的二进制表示中至少有一位是1.  
    假设这个数的最右边一位是1，那么减去1时，最后一位变成0而其他所有位都保持不变。也就是最后一位相当于做了取反操作，由1变成0.
 *  假设最后一位不是1而是0，如果该整数的二进制表示中最右边的1位于第m位，那么减去1时，第m位由1变成0，而第m位之后的所有0变成1，整数中第m位之前的所有位保持不变。

**例如：**  
一个二进制数1100，它的第二位是从最右边数起的一个1.减去1后，第二位变成0，它后面的两位0变为1，前面的1保持不变，得到结果1011.

**总结：**  
把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0，那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。  
**实现**（想计算一下每个循环的次数，但好像有些问题）

ackage ti15;
    
    public class Lian {
    	//法一
    	public int fun(int num){
    		int count = 0;
    		int times = 0;
    		while(num != 0){
    			if((num & 1) == 1){
    				count ++;
    				times = times + 1;
    			}
    			num = num >>1;
    		}
    		System.out.println("循环"+times+"次");
    		return count ;
    	}
    	
    	//法二
    	public int fun1(int num){
    		int count = 0;
    		int flag = 1;
    		int times1 = 0;
    		while(flag != 0){
    			if((flag & num) != 0){
    				count++;
    				times1 = times1 + 1;
    			}
    			flag = flag <<1;
    		}
    		System.out.println("循环"+times1+"次");
    		return count;
    	}
    	
    	//法3
    	public int fun2(int num){
    		int count = 0;
    		int times2 = 0;
    		while(num != 0){
    			count ++;
    			times2 = times2+1;
    			num = num & (num -1);
    		}
    		System.out.println("循环"+times2+"次");
    		return count;
    	}
    	public static void main(String[] args) {
    		Lian lx = new Lian();
    		int n = 9;
    		System.out.println(lx.fun(n));//2
    		System.out.println(lx.fun1(n));//2
    		System.out.println(lx.fun2(n));//2
    		System.out.println("*********");
    		int n1 = 0x7FFFFFFF;
    		System.out.println(lx.fun(n1));//31
    		System.out.println(lx.fun1(n1));//31
    		System.out.println(lx.fun2(n1));//31
    		System.out.println("***********");
    		//int n2 = 0x80000000;
    		//System.out.println(lx.fun(n2));
    		int n3 = 12;
    		System.out.println(lx.fun(n3));
    		System.out.println(lx.fun1(n3));
    		System.out.println(lx.fun2(n3));
    		System.out.println("*********");
    	}
    	
    }

**【相关题目】**  
1.用一条语句判断一个整数是不是2的整数次方。一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。根据前面分析，把这个整数减去1之后再和它自己做与运算。这个整数中唯一的1就会变成0.

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

**【举一反三】**  
把一个整数减去1之后再和原来的整数做位于运算，得到的结果相当于把整数的二进制表示中最右边的1变成0.很多二进制的问题都可以用这种思路解决。

参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/weixin\_37672169/article/details/80148443][https_blog.csdn.net_weixin_37672169_article_details_80148443]

[20190112154454198.png]: /images/20220327/3b57c54235fa4fc795c027f437785e5c.png
[20190112154543766.png]: /images/20220327/01cbaea24da24c0bb08f10e5aa382953.png
[20190112154627570.png]: /images/20220327/120aaa14e0954a819b2735f5dab63412.png
[https_blog.csdn.net_weixin_37672169_article_details_80148443]: https://blog.csdn.net/weixin_37672169/article/details/80148443