Question

Write a recursive method that returns the number of 1’s in the binary representation of N. Use the fact that this is equal to the number of 1’s in the representation of N/2, plus 1, if N is odd

Answer 1

Answer:

Here is the recursive method NoOfOnes :

public static int NoOfOnes(int N)    { // method that takes number N as argument and returns the number of 1’s in the binary representation of N

       if(N==0)  { //base case 1

           return 0;        } //if the value of N is equal to 0 then method returns 0

       else if(N==1){ //base case 2

           return 1;        } // if the value of N is equal to 1 then method returns 1

       else if(N%2==1)  { //if N is odd (recursive case)

           return NoOfOnes(N/2)+1;   } //calls method recursively and divides N by 2 plus 1

       else{ //when N i even (recursive case)

           return NoOfOnes(N/2);   }   }   //calls method recursively and divides N by 2  to return number of 1's in binary representation of N

Explanation:

Here is the complete JAVA program:

import java.util.Scanner; //to take input from user

public class Main {

   public static int NoOfOnes(int N)    {//the method that takes number N as argument and returns the number of 1’s in the binary representation of N

       if(N==0)  { //base case 1

           return 0;        }

       else if(N==1){//base case 2

           return 1;        }

       else if(N%2==1)  {//recursive case when N is odd

           return NoOfOnes(N/2)+1;   }

       else{ //recursive case when N is even

           return NoOfOnes(N/2);   }   }    

public static void main(String[] args) { //start of main function

       Scanner scan = new Scanner(System.in); //creates object of Scanner

       System.out.print("Enter n: ");//prompts user to enter value of N

       int n = scan.nextInt(); //reads the value of n from use

 System.out.print("number of 1’s in the binary representation of " +n+" is: "+NoOfOnes(n)); } } //displays the number of 1’s in the binary representation of n

i will explain the working of the function with an example

Lets say N = 6

if(N==0) this statement evaluates to false as N is not 0

else if(N==1 this statement also evaluates to false as N is not 1

else if(N%2==1) this statement also evaluates to false because N is not odd. If we take modulo of 6 by 2 then the remainder is 0 because 6 is completely divisible by 2 so N = 6 is an even number. So the else part is executed:  

       else{

           return NoOfOnes(N/2);}

This statement calls NoOfOnes recursive by passing N/2 to the method. So this becomes:

return NoOfOnes(6/2)

6/2 = 3

NoOfOnes(3)

Now this method is called again with the value of N = 3. Since 3 is an odd number so the recursive case of odd N is executed:

else if(N%2==1)  {

           return NoOfOnes(N/2)+1;   }

NoOfOnes(3/2)+ 1

NoOfOnes(1) + 1

Now the method is called again with value of N=1. The base case 2 is executed because N==1 which returns 1

else if(N==1){

           return 1;   }

So this becomes

NoOfOnes(1) + 1

1 + 1

= 2

So the method return 2 as the number of 1’s in the binary representation of N = 6

Hence the output of the above program with N = 6 is

number of 1’s in the binary representation of 6 is: 2