Cuente el número de pasos requeridos para reducir N a 1 siguiendo cierta regla

Dado un entero positivo  . Encuentre la cantidad de pasos necesarios para minimizarlo a 1. En un solo paso , N se redujo a la mitad si es una potencia de 2; de lo contrario, N se reduce a la diferencia de N y su potencia de 2 más cercana, que es más pequeña que N.
Ejemplos: 
 

Input : N = 2
Output : 1

Input : N = 20
Output : 3

Enfoque simple: según la pregunta, un enfoque muy simple y de fuerza bruta es iterar sobre N hasta que se reduzca a 1, donde la reducción involucra dos casos: 
 

1. N es potencia de 2: reduce n a n/2
2. N no es potencia de 2: reduce n a n – (2^log2(n))

Enfoque eficiente: Antes de continuar con el resultado real, echemos un vistazo a la representación de bits de un número entero n según la declaración del problema. 
 

1. Cuando un número entero es potencia de 2: En este caso, la representación de bit incluye solo un bit establecido y ese también queda más. Por lo tanto, log2(n), es decir, la posición de bit menos uno es el número de pasos necesarios para reducirlo a n. Que también es igual al número de bits establecidos en n-1.
2. Cuando un número entero no es potencia de 2: El resto de n – 2^(log2(n)) es igual a un número entero que se puede obtener desactivando el bit establecido más a la izquierda. Por lo tanto, la eliminación de un bit establecido cuenta como un paso en este caso.

Por lo tanto, la respuesta real para los pasos necesarios para reducir n es igual al número de bits establecidos en n-1 . Que se puede calcular fácilmente ya sea usando el bucle o cualquiera de los métodos descritos en la publicación: Count Set bits in an Integer .
A continuación se muestra la implementación del enfoque anterior: 
 

// Cpp to find the number of step to reduce n to 1
// C++ program to demonstrate __builtin_popcount()
#include <iostream>
using namespace std;
 
// Function to return number of steps for reduction
int stepRequired(int n)
{
    // builtin function to count set bits
    return __builtin_popcount(n - 1);
}
 
// Driver program
int main()
{
    int n = 94;
    cout << stepRequired(n) << endl;
    return 0;
}

// Java program to find the number of step to reduce n to 1
 
import java.io.*;
class GFG
{
    // Function to return number of steps for reduction
    static int stepRequired(int n)
    {
        // builtin function to count set bits
        return Integer.bitCount(n - 1);
    }
     
    // Driver program
    public static void  main(String []args)
    {
        int n = 94;
        System.out.println(stepRequired(n));
     
    }
}
 
 
// This code is contributed by
// ihritik

# Python3 to find the number of step
# to reduce n to 1
# Python3 program to demonstrate
# __builtin_popcount()
 
# Function to return number of
# steps for reduction
def stepRequired(n) :
 
    # step to count set bits
    return bin(94).count('1')
 
# Driver Code
if __name__ == "__main__" :
 
    n = 94
    print(stepRequired(n))
 
# This code is contributed by Ryuga

// C# program to find the number of step to reduce n to 1
 
using System;
class GFG
{
     
    // function to count set bits
    static int countSetBits(int n)
    {
   
        // base case
        if (n == 0)
            return 0;
   
        else
   
            // if last bit set
            // add 1 else add 0
            return (n & 1) + countSetBits(n >> 1);
    }
    // Function to return number of steps for reduction
    static int stepRequired(int n)
    {
      
        return countSetBits(n - 1);
    }
     
    // Driver program
    public static void Main()
    {
        int n = 94;
        Console.WriteLine(stepRequired(n));
     
    }
}
 
 
// This code is contributed by
// ihritik

<?php
// PHP program to find the number of step to reduce n to 1
 
// recursive function to
// count set bits
function countSetBits($n)
{
    // base case
    if ($n == 0)
        return 0;
    else
        return 1 + 
          countSetBits($n & 
                      ($n - 1));
}
 
// Function to return number of steps for reduction
function stepRequired($n)
{
  
    return countSetBits($n - 1);
}
     
// Driver program
 
$n = 94;
echo stepRequired($n);
 
 
 
// This code is contributed by
// ihritik
 
?>

<script>
    // Javascript program to find the number of step to reduce n to 1
     
    // function to count set bits
    function countSetBits(n)
    {
     
        // base case
        if (n == 0)
            return 0;
     
        else
     
            // if last bit set
            // add 1 else add 0
            return (n & 1) + countSetBits(n >> 1);
    }
    // Function to return number of steps for reduction
    function stepRequired(n)
    {
        
        return countSetBits(n - 1);
    }
     
    let n = 94;
      document.write(stepRequired(n));
 
// This code is contributed by decode2207.
</script>

5