剑指Offer面试题10（Java版）：二进制中的1的个数

ゝ一世哀愁。 2022-07-16 04:53 115阅读 0赞

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

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

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

int numberOf1(int n)

int count = 0;

while(n!=0)\{

if(n & 1)

count++;

n = n>>1;

return count;

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

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

**2、常规解法：**

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

int number1(int n)\{

int count = 0;

int flag= 1;

while(flag ! =0)\{

if(n& flag)

count++;

flag =flag <<1;

return count;

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

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

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

**\[html\]**  [view plain][]   [copy][view plain]

1.  /\*\*  
2.   \*题目：实现一个函数，输入一个整数，输出该数二进制表示中的1的个数。  
3.   \*例如把9改成二进制是1001，有2位是1.因此如果输入9，该函数输出2.   
4.   \*/  
5.  package swordForOffer;  
6.    
7.  /\*\*  
8.   \* @author JInShuangQi  
9.   \*  
10.  \*         2015年7月30日  
11.  \*/  
12. public class E10NumberOf1InBinary \{  
13.     public int numberOf1(int num) \{  
14.         int count = 0;  
15.         while (num != 0) \{  
16.             count++;  
17.             num = num & (num - 1);  
18.   
19.         \}  
20.         return count;  
21.     \}  
22.   
23.     public static void main(String\[\] args) \{  
24.         E10NumberOf1InBinary test = new E10NumberOf1InBinary();  
25.         System.out.println(test.numberOf1(9));  
26.     \}  
27. \}  
28.

[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47143127#