Potencias de 2 a la suma requerida usando enmascaramiento de bits

Dado un número entero N , la tarea es encontrar los números que cuando se suman después de ser elevados a la potencia de 2 dan el número entero N .
Ejemplos: 
 

Entrada: N = 12345 
Salida: 0, 3, 4, 5, 12, 13 
Explicación: 
12345 = 2^0 + 2^3 + 2^4 + 2^5 + 2^12 + 2^13
Entrada: N = 10000 
Salida: 4, 8, 9, 10, 13 
Explicación: 
10000 = 2^4 + 2^8 + 2^9 + 2^10 + 2^13 
 

Acercarse: 
 

• Dado que cada número se puede expresar como suma de potencias de 2, la tarea es imprimir cada i cuando el i ^-ésimo bit se establece en la representación binaria de N.
•  

Ilustración: 
(29) ₁₀ = (11101) ₂ 
Así, en 29, {0, 2, 3, 4} son los índices de los bits establecidos. 
2 ⁰ + 2 ² + 2 ³ + 2 ⁴ 
= 1 + 4 + 8 + 16 
= 29 
 

•  
• Para verificar si el i ^-ésimo bit está configurado, solo necesitamos verificar: 
   

if( N & (1 << i) ) == 1 
Ilustración: 
(29) ₁₀ = (11101) ₂ 
0 ^° bit: 11101 & 1 = 1 
1 ^° bit: 11101 & 10 = 0 
2 ^° bit: 11101 & 100 = 1 
3er bit: ¹¹¹⁰¹ y 1000 = 1 
4to bit: ¹¹¹⁰¹ y 10000 = 1 
 

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

// C++ Program to split N
// into numbers which when
// added after being raised
// to the power of 2 gives N
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the numbers
// which raised to power of 2
// adds up to N
void PowerOfTwo(long long N)
{
    for (int i = 0; i < 64; i++) {
        long long x = 1;
 
        // Checking if i-th bit is
        // set in N or not by
        // shifting 1 i bits to
        // the left and performing
        // AND with N
        if (N & (x << i))
            cout << i << " ";
    }
}
 
// Driver Code
int main()
{
 
    long long N = 12345;
    PowerOfTwo(N);
 
    return 0;
}

// Java Program to split N
// into numbers which when
// added after being raised
// to the power of 2 gives N
class GFG{
 
// Function to print the numbers
// which raised to power of 2
// adds up to N
static void PowerOfTwo(long N)
{
    for (int i = 0; i < 64; i++)
    {
        long x = 1;
 
        // Checking if i-th bit is
        // set in N or not by
        // shifting 1 i bits to
        // the left and performing
        // AND with N
        if ((N & (x << i)) > 0)
            System.out.print(i + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    long N = 12345;
    PowerOfTwo(N);
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to split N
# into numbers which when
# added after being raised
# to the power of 2 gives N
 
# Function to print the numbers
# which raised to power of 2
# adds up to N
def PowerOfTwo(N):
 
    for i in range(0, 64):
        x = 1
         
        # Checking if i-th bit is
        # set in N or not by
        # shifting 1 i bits to
        # the left and performing
        # AND with N
        if (N & (x << i)) > 0:
            print(i, end = " ")
         
# Driver Code
if __name__ == "__main__":
     
    # Given number
    N = 12345;
 
    # Function call
    PowerOfTwo(N)
 
# This code is contributed by rock_cool

// C# Program to split N
// into numbers which when
// added after being raised
// to the power of 2 gives N
using System;
class GFG{
 
// Function to print the numbers
// which raised to power of 2
// adds up to N
static void PowerOfTwo(long N)
{
    for (int i = 0; i < 64; i++)
    {
        long x = 1;
 
        // Checking if i-th bit is
        // set in N or not by
        // shifting 1 i bits to
        // the left and performing
        // AND with N
        if ((N & (x << i)) > 0)
            Console.Write(i + " ");
    }
}
 
// Driver Code
public static void Main()
{
    long N = 12345;
    PowerOfTwo(N);
}
}
 
// This code is contributed by Nidhi_biet

<script>
 
// Javascript Program to split N
// into numbers which when
// added after being raised
// to the power of 2 gives N
 
// Function to print the numbers
// which raised to power of 2
// adds up to N
function PowerOfTwo(N)
{
    for (var i = 0; i < 64; i++) {
        var x = 1;
 
        // Checking if i-th bit is
        // set in N or not by
        // shifting 1 i bits to
        // the left and performing
        // AND with N
        if ((N & (x * Math.pow(2,i))) >0)
            document.write( i + " ");
    }
}
 
// Driver Code
var N = 12345;
PowerOfTwo(N);
 
// This code is contributed by importantly.
</script>

0 3 4 5 12 13

Complejidad de tiempo: O(log N) 
Complejidad de espacio: O(1)
Para un enfoque alternativo, consulte Potencias de 2 para la suma requerida