Imprimir todas las submáscaras de una máscara dada

Dado un número entero N , la tarea es imprimir todos los subconjuntos del conjunto formado por los bits del conjunto presentes en la representación binaria de N.

Ejemplos:

Entrada: N = 5
Salida: 5 4 1 
Explicación:
La representación binaria de N es “101”, por lo tanto todos los subconjuntos requeridos son {“101”, “100”, “001”, “000”}.

Entrada: N = 25
Salida: 25 24 17 16 9 8 1 
Explicación:
La representación binaria de N es “11001”. Por lo tanto, todos los subconjuntos requeridos son {“11001”, “11000”, “10001”, “10000”, “01001”, “01000”, “0001”, “0000”}.

Enfoque ingenuo: el enfoque más simple es atravesar cada máscara en el rango [0, 1 << (recuento de bits establecidos en N ) ] y verificar si no hay otros bits establecidos excepto los bits en N. Luego, imprímelo. 
Complejidad de tiempo: O(2 ^{(recuento de bits establecidos en N)} )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar al atravesar solo las submáscaras que son el subconjunto de la máscara N .

• Supongamos que S es la submáscara actual, que es el subconjunto de la máscara N. Entonces, se puede observar que asignando S = (S – 1) & N , se puede obtener la siguiente submáscara de N que es menor que S .
• En S – 1 , voltea todos los bits presentes a la derecha del bit establecido más a la derecha, incluido el bit establecido más a la derecha de S.
• Por lo tanto, después de realizar Bitwise & con N , se obtiene una submáscara de N.
• Por lo tanto, S = (S – 1) & N da la siguiente submáscara de N que es menor que S.

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos S = N.
• Iterar mientras S > 0 y en cada iteración, imprimir el valor de S .
• Asigne S = (S – 1) y N.

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

// C++ Program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the submasks of N
void SubMasks(int N)
{
    for (int S = N; S; S = (S - 1) & N) {
        cout << S << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 25;
    SubMasks(N);
 
    return 0;
}

// Java Program for above approach
import java.util.*;
class GFG
{
   
// Function to print the submasks of N
static void SubMasks(int N)
{
    for (int S = N; S > 0; S = (S - 1) & N)
    {
        System.out.print(S + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int N = 25;
    SubMasks(N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

# Python3 program for the above approach
 
# Function to print the submasks of N
def SubMasks(N) :
    S = N
    while S > 0:
        print(S,end=' ')
        S = (S - 1) & N
 
# Driven Code
if __name__ == '__main__':
    N = 25
    SubMasks(N)
     
    # This code is contributed by bgangwar59.

// C# program for the above approach
using System;
 
class GFG{
 
// Function to print the submasks of N
static void SubMasks(int N)
{
    for (int S = N; S > 0; S = (S - 1) & N)
    {
        Console.Write(S + " ");
    }
}
 
// Driver Code
static public void Main()
{
    int N = 25;
    SubMasks(N);
}
}
 
// This code is contributed by Code_hunt.

<script>
 
// JavaScript program of the above approach
 
// Function to print the submasks of N
function SubMasks(N)
{
    for (let S = N; S > 0; S = (S - 1) & N)
    {
        document.write(S + " ");
    }
}
 
    // Driver Code
     
    let N = 25;
    SubMasks(N);
 
</script>

25 24 17 16 9 8 1

Complejidad de tiempo: O(2 ^{(recuento de bits establecidos en N)} )
Espacio auxiliar: O(1)