Números de 1 a n bits sin 1 consecutivos en representación binaria – Part 1

Dado un número n, nuestra tarea es encontrar todos los números de 1 a n bits sin 1 consecutivos en su representación binaria.
Ejemplos:

Input: N = 4
Output: 1 2 4 5 8 9 10
These are numbers with 1 to 4
bits and no consecutive ones in
binary representation.

Input: n = 3
Output: 1 2 4 5

Acercarse:

1. Habrá 2 ⁿ números con un número de bits de 1 a n.
2. Iterar a través de los 2 ⁿ números. Para cada número, compruebe si contiene bits de conjunto consecutivos o no. Para verificar, lo hacemos bit a bit y del número actual i y i desplazado a la izquierda. Si bit a bit y contiene un bit distinto de cero (o su valor es distinto de cero), entonces el número dado contiene bits de conjunto consecutivos.

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

// Print all numbers upto n bits
// with no consecutive set bits.
#include<iostream>
using namespace std;
 
void printNonConsecutive(int n)
{
    // Let us first compute
    // 2 raised to power n.
    int p = (1 << n);
 
    // loop 1 to n to check
    // all the numbers
    for (int i = 1; i < p; i++)
 
        // A number i doesn't contain
        // consecutive set bits if
        // bitwise and of i and left
        // shifted i do't contain a
        // commons set bit.
        if ((i & (i << 1)) == 0)
            cout << i << " ";
}
 
// Driver code
int main()
{
    int n = 3;
    printNonConsecutive(n);
    return 0;
}

// Java Code to Print all numbers upto
// n bits with no consecutive set bits.
import java.util.*;
 
class GFG
{
    static void printNonConsecutive(int n)
        {
            // Let us first compute
            // 2 raised to power n.
            int p = (1 << n);
 
            // loop 1 to n to check
            // all the numbers
            for (int i = 1; i < p; i++)
 
            // A number i doesn't contain
            // consecutive set bits if
            // bitwise and of i and left
            // shifted i do't contain a
            // commons set bit.
            if ((i & (i << 1)) == 0)
                System.out.print(i + " ");
         
        }
 
// Driver code
public static void main(String[] args)
    {
        int n = 3;
        printNonConsecutive(n);
    }
}
 
// This code is contributed by Mr. Somesh Awasthi

# Python3 program to print all numbers upto
# n bits with no consecutive set bits.
 
def printNonConsecutive(n):
 
    # Let us first compute 
    # 2 raised to power n.
    p = (1 << n)
 
    # loop 1 to n to check
    # all the numbers
    for i in range(1, p):
 
        # A number i doesn't contain
        # consecutive set bits if
        # bitwise and of i and left
        # shifted i do't contain a
        # common set bit.
        if ((i & (i << 1)) == 0):
            print(i, end = " ")
 
# Driver code
n = 3
printNonConsecutive(n)
 
# This code is contributed by Anant Agarwal.

// C# Code to Print all numbers upto
// n bits with no consecutive set bits.
using System;
 
class GFG
{
    static void printNonConsecutive(int n)
    {
        // Let us first compute
        // 2 raised to power n.
        int p = (1 << n);
 
        // loop 1 to n to check
        // all the numbers
        for (int i = 1; i < p; i++)
 
            // A number i doesn't contain
            // consecutive set bits if
            // bitwise and of i and left
            // shifted i do't contain a
            // commons set bit.
            if ((i & (i << 1)) == 0)
                Console.Write(i + " ");
         
    }
 
// Driver code
public static void Main()
    {
        int n = 3;
        printNonConsecutive(n);
    }
}
// This code is contributed by nitin mittal.

<?php
// Print all numbers upto n bits
// with no consecutive set bits.
 
function printNonConsecutive($n)
{
     
    // Let us first compute
    // 2 raised to power n.
    $p = (1 << $n);
 
    // loop 1 to n to check
    // all the numbers
    for ($i = 1; $i < $p; $i++)
 
        // A number i doesn't contain
        // consecutive set bits if
        // bitwise and of i and left
        // shifted i do't contain a
        // commons set bit.
        if (($i & ($i << 1)) == 0)
            echo $i . " ";
}
 
    // Driver code
    $n = 3;
    printNonConsecutive($n);        
     
// This code is contributed by Sam007
?>

<script>
 
// Javascript Code to Print all numbers upto
// n bits with no consecutive set bits.
 
function printNonConsecutive(n)
        {
            // Let us first compute
            // 2 raised to power n.
            let p = (1 << n);
 
            // loop 1 to n to check
            // all the numbers
            for (let i = 1; i < p; i++)
 
            // A number i doesn't contain
            // consecutive set bits if
            // bitwise and of i and left
            // shifted i do't contain a
            // commons set bit.
            if ((i & (i << 1)) == 0)
                document.write(i + " ");
         
        }
 
// driver program
 
        let n = 3;
        printNonConsecutive(n);
         
</script>

1 2 4 5 

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Este artículo es una contribución de Devanshu Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.