Pasos máximos para transformar 0 a X con AND bit a bit

Para un número entero N, hay elementos que van de 0 a N-1. Ciertos elementos se pueden transformar en otros elementos. Cada transformación requiere un cierto esfuerzo que es igual a 1 unidad, para cada transformación. Un elemento A puede transformarse en un elemento B, si y solo si A != B y A & B = A (donde & es el operador AND bit a bit). Necesitamos encontrar el máximo esfuerzo posible para obtener el elemento con valor X, del elemento con valor 0, mediante una serie de transformaciones.
Ejemplos: 
 

Entrada: X = 2 
Salida: 1 
La única forma de obtener 2 es transformar directamente 0 en 2 (Y bit a bit de 0 y 2 es 0) y, por lo tanto, requiere un paso. 
Entrada: X = 3 
Salida: 2 
3 se puede obtener en dos pasos. Primero, transforme 0 a 1 (Y bit a bit de 0 y 1 es 0). Luego, transforme 1 a 3 (Y bit a bit de 1 y 3 es 1).

La solución simple es contar el número de bits establecidos en X. 
Explicación: 
primero, considere una transformación de un solo paso de A a B. Todos los bits establecidos (bits que son iguales a 1) de A deben establecerse en B, de lo contrario bit a bit AND de A y B no será igual a A. Si hay algún bit que está establecido en A pero no en B, entonces la transformación no es posible. Los bits no configurados de A pueden configurarse o desconectarse en B, no importa. Luego podemos cambiar A a B configurando todos los bits no configurados en A en un solo paso. En consecuencia, si tuviéramos que transformar 0 en X en los pasos más pequeños, la respuesta habría sido uno porque el AND bit a bit de 0 con cualquier número es 0. 
Pero tenemos que calcular los pasos máximos. Entonces, en cada paso, configuramos cada bit comenzando desde la derecha y un bit establecido no se puede borrar una vez que se establece. 
Ejemplo: 
Supongamos que queremos obtener 13 (1101 en binario) de 0. Comenzamos configurando el 1er bit de la derecha transformando 0 en 1 (0001 en binario). A continuación, configuramos el tercer bit desde la derecha para formar 5 (0101 en binario). El último paso sería establecer el 4º bit y obtener 13 (1101).
 

// CPP code to find the maximum possible
// effort
#include <bits/stdc++.h>
using namespace std;
 
// Function to get no of set bits in binary
// representation of positive integer n
unsigned int countSetBits(unsigned int n)
{
    unsigned int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Driver code
int main()
{
    int i = 3;
    cout << countSetBits(i);
    return 0;
}

// Java code to find the maximum
// possible effort
 
class GFG {
     
// Function to get no. of
// set bits in binary
// representation of
// positive integer n
static int countSetBits(int n)
{
    int count = 0;
    while (n != 0)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int i = 3;
    System.out.print(countSetBits(i));
}
}
 
// This code is contributed by Smitha.

# Python3 code to find the
# maximum possible effort
   
# Function to get no of
# set bits in binary
# representation of positive
# integer n
def countSetBits(n) :
    count = 0
    while (n) :
        count += n & 1
        n >>= 1
    return count
   
# Driver code
i = 3
print (countSetBits(i))
   
# This code is contributed by
# Manish Shaw(manishshaw1)

// C# code to find the maximum
// possible effort
using System;
 
class GFG {
     
// Function to get no. of
// set bits in binary
// representation of
// positive integer n
static int countSetBits(int n)
{
    int count = 0;
    while (n != 0)
    {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
    int i = 3;
    Console.Write(countSetBits(i));
}
}
 
// This code is contributed by Smitha.

<?php
// PHP code to find the
// maximum possible effort
 
// Function to get no of
// set bits in binary
// representation of positive
// integer n
function countSetBits($n)
{
    $count = 0;
    while ($n)
    {
        $count += $n & 1;
        $n >>= 1;
    }
    return $count;
}
 
// Driver code
$i = 3;
echo (countSetBits($i));
 
// This code is contributed by
// Manish Shaw(manishshaw1)
?>

<script>
  
// JavaScript code to find the maximum possible
// effort
 
// Function to get no of set bits in binary
// representation of positive integer n
function countSetBits(n)
{
    var count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}
 
// Driver code
var i = 3;
document.write( countSetBits(i));
 
</script>

Producción:  

2

Complejidad de tiempo: O (log ₁₀ N)

Espacio Auxiliar: O(1)