编写一个递归方法，返回数N的二进制表示中1的个数

太过爱你忘了你带给我的痛 2022-06-12 05:15 36阅读 0赞

问题：编写一个递归方法，返回数N的二进制表示中1的个数

解决：利用这样一个事实：如果N是奇数，那么它等于N/2的二进制表示中1的个数加1。

通过自己笔算还能发现，如果N是偶数，那么它的个数等于，N一直除以2直到变成一个奇数，这个奇数的个数。

第一个版本：

package firstCHA;
    
    public class two1num {
    
    	public static int trans(int num)
    	{
    		if(num==0)
    			return 0;
    		else if(num%2!=0)  //如果传入一个奇数
    		{
    			return trans(num/2)+1;
    		}
    		else //如果传入一个偶数
    		{
    			return trans(num/2);
    		}
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		System.out.println(trans(35));
    	
    	}
    
    }

第二个版本：

package firstCHA;
    
    public class two1num_2 {
    
    	public static int trans(int num)
    	{
    		if(num==0)
    			return 0;
    		else if(num%2!=0) //如果传入一个奇数
    		{
    			return trans(num/2)+1;
    		}
    		else //如果传入一个偶数
    		{
    			while(num%2==0)
    			{
    				num=num/2;
    			}
    			return trans(num); //经过循环已经变成奇数，不能再除以2，应该直接递归了，好让结果加一
    		}
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		System.out.println(trans(35));
    	
    	}
    
    }

第三个版本：代码最少的版本

package firstCHA;
    
    public class two1num_3 {
    	public static int ones( int n )
    	{
    	if( n < 2 ) //递归终点有两个，n为1则返回1，n为0则返回0
    	return n;
    	return n % 2 + ones( n / 2 );//此为递归过程，如果为奇数，结果加1，如果为偶数，结果加0（因为偶数和偶数/2，这两者的1的个数都是一样的）。但总之都得递归下去
    	}
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		System.out.println(ones(35));
    	}
    
    }

思考：1.要通过已知条件来发现新的规律，比如题中已经给了N为奇数的情况，而N为偶数的情况则需要我们自己去思考出来。

2.第三个版本是原题答案，不得不说很佩服，能写得这么简洁，思路清晰。