Encuentra todas las potencias de 2 menores o iguales a un número dado

Dado un número N positivo , la tarea es encontrar todas las potencias perfectas de dos que son menores o iguales que el número N dado .

Ejemplos:

Entrada: N = 63
Salida: 32 16 8 4 2 1
Explicación:
Hay un total de 6 potencias de 2, que son menores o iguales que el número dado N.

Entrada: N = 193
Salida: 128 64 32 16 8 4 2 1
Explicación:
Hay un total de 8 potencias de 2, que son menores o iguales que el número dado N.

Enfoque ingenuo: la idea es atravesar cada número de N a 1 y verificar si es una potencia perfecta de 2 o no. En caso afirmativo, imprima ese número.

Otro enfoque: la idea es encontrar todas las potencias de 2 y simplemente imprimir las potencias que son menores o iguales que N.

Otro enfoque: la idea se basa en el concepto de que todas las potencias de 2 tienen todos los bits configurados, en su forma binaria. La función Bitset se utiliza en este enfoque para resolver el problema anterior. A continuación se muestran los pasos:

1. Encuentre la mayor potencia de 2 (digamos temp ) que se usa para evaluar el número menor o igual que N.
2. Inicialice una array de conjunto de bits arr[] de tamaño máximo 64 , para almacenar la representación binaria del número dado N .
3. Restablezca todos los bits en la array de conjunto de bits usando la función restablecer() .
4. Iterar un ciclo desde el total hasta 0 , y secuencialmente hacer que cada bit sea 1 , y encontrar el valor de esa expresión binaria y luego restablecer el bit.

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

// C++ program for the above approach
  
#include <bits/stdc++.h>
using namespace std;
const int MAX = 64;
  
// Function to return max exponent of
// 2 which evaluates a number less
// than or equal to N
int max_exponent(int n)
{
    return (int)(log2(n));
}
  
// Function to print all the powers
// of 2 less than or equal to N
void all_powers(int N)
{
    bitset<64> arr(N);
  
    // Reset all the bits
    arr.reset();
  
    int total = max_exponent(N);
  
    // Iterate from total to 0
    for (int i = total; i >= 0; i--) {
  
        // Reset the next bit
        arr.reset(i + 1);
  
        // Set the current bit
        arr.set(i);
  
        // Value of the binary expression
        cout << arr.to_ulong() << " ";
    }
}
  
// Driver Code
int main()
{
    // Given Number
    int N = 63;
  
    // Function Call
    all_powers(N);
    return 0;
}

32 16 8 4 2 1

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)