Cuente Set-bits de número usando Recursion

Dado un número N. La tarea es encontrar el número de bits establecidos en su representación binaria usando recursividad.

Ejemplos: 

Entrada: 21 
Salida: 3 
21 representado como 10101 en representación binaria

Entrada: 16 
Salida: 1 
16 representado como 10000 en representación binaria 

Acercarse:  

1. Primero, verifique el LSB del número.
2. Si el LSB es 1, sumamos 1 a nuestra respuesta y dividimos el número entre 2.
3. Si el LSB es 0, sumamos 0 a nuestra respuesta y dividimos el número por 2.
4. Luego seguimos recursivamente el paso (1) hasta que el número sea mayor que 0.

A continuación se muestra la implementación del enfoque anterior:  

// CPP program to find number
// of set bist in a number
#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find
// number of set bist in a number
int CountSetBits(int n)
{
    // Base condition
    if (n == 0)
        return 0;
         
    // If Least significant bit is set
    if((n & 1) == 1)
        return 1 + CountSetBits(n >> 1);
     
    // If Least significant bit is not set
    else
        return CountSetBits(n >> 1);
}
 
// Driver code
int main()
{
    int n = 21;
     
    // Function call
    cout << CountSetBits(n) << endl;
 
    return 0;
}

// Java program to find number
// of set bist in a number
class GFG
{
    // Recursive function to find
    // number of set bist in a number
    static int CountSetBits(int n)
    {
        // Base condition
        if (n == 0)
            return 0;
             
        // If Least significant bit is set
        if((n & 1) == 1)
            return 1 + CountSetBits(n >> 1);
         
        // If Least significant bit is not set
        else
            return CountSetBits(n >> 1);
    }
     
    // Driver code
    public static void main (String [] args)
    {
        int n = 21;
         
        // Function call
        System.out.println(CountSetBits(n));
    }
}
 
// This code is contributed by ihritik

# Python3 program to find number
# of set bist in a number
 
# Recursive function to find
# number of set bist in a number
def CountSetBits(n):
     
    # Base condition
    if (n == 0):
        return 0;
         
    # If Least significant bit is set
    if((n & 1) == 1):
        return 1 + CountSetBits(n >> 1);
     
    # If Least significant bit is not set
    else:
        return CountSetBits(n >> 1);
 
# Driver code
if __name__ == '__main__':
    n = 21;
     
    # Function call
    print(CountSetBits(n));
 
# This code is contributed by 29AjayKumar

// C# program to find number
// of set bist in a number
using System;
 
class GFG
{
    // Recursive function to find
    // number of set bist in a number
    static int CountSetBits(int n)
    {
        // Base condition
        if (n == 0)
            return 0;
             
        // If Least significant bit is set
        if((n & 1) == 1)
            return 1 + CountSetBits(n >> 1);
         
        // If Least significant bit is not set
        else
            return CountSetBits(n >> 1);
    }
     
    // Driver code
    public static void Main ()
    {
        int n = 21;
         
        // Function call
        Console.WriteLine(CountSetBits(n));
    }
}
 
// This code is contributed by ihritik

<script>
 
// Javascript program to find number
// of set bist in a number
 
// Recursive function to find
// number of set bist in a number
function CountSetBits(n)
{
     
    // Base condition
    if (n == 0)
        return 0;
         
    // If Least significant bit is set
    if ((n & 1) == 1)
        return 1 + CountSetBits(n >> 1);
     
    // If Least significant bit is not set
    else
        return CountSetBits(n >> 1);
}
 
// Driver code
var n = 21;
 
// Function call
document.write(CountSetBits(n));
 
// This code is contributed by Amit Katiyar
 
</script>

3

Complejidad de tiempo: O (log n)

Espacio Auxiliar: O(log n)