Imprime los primeros n números con exactamente dos bits establecidos

Dado un número n, imprima los primeros n enteros positivos con exactamente dos bits establecidos en su representación binaria.
Ejemplos: 
 

Input: n = 3
Output: 3 5 6
The first 3 numbers with two set bits are 3 (0011),
5 (0101) and 6 (0110)

Input: n = 5
Output: 3 5 6 9 10 12

Una solución simple es considerar todos los enteros positivos uno por uno a partir de 1. Para cada número, verifique si tiene exactamente dos conjuntos de bits. Si un número tiene exactamente dos bits establecidos, imprímalo e incremente el conteo de dichos números.
Una solución eficiente es generar directamente dichos números. Si observamos claramente los números, podemos reescribirlos como se indica a continuación pow(2,1)+pow(2,0), pow(2,2)+pow(2,0), pow(2,2)+pow (2,1), pow(2,3)+pow(2,0), pow(2,3)+pow(2,1), pow(2,3)+pow(2,2), …… …
Todos los números se pueden generar en orden creciente según el mayor de los dos bits establecidos. La idea es arreglar más de dos bits uno por uno. Para el bit establecido más alto actual, considere todos los bits más bajos e imprima los números formados.
 

C++

// C++ program to print first n numbers
// with exactly two set bits
#include <iostream>
using namespace std;
 
// Prints first n numbers with two set bits
void printTwoSetBitNums(int n)
{
    // Initialize higher of two sets bits
    int x = 1;
 
    // Keep reducing n for every number
    // with two set bits.
    while (n > 0)
    {
        // Consider all lower set bits for
        // current higher set bit
        int y = 0;
        while (y < x)
        {
            // Print current number
            cout << (1 << x) + (1 << y) << " ";
 
            // If we have found n numbers
            n--;
            if (n == 0)
                return;
 
            // Consider next lower bit for current
            // higher bit.
            y++;
        }
 
        // Increment higher set bit
        x++;
    }
}
 
// Driver code
int main()
{
    printTwoSetBitNums(4);
 
    return 0;
}

Java

// Java program to print first n numbers
// with exactly two set bits
import java.io.*;
 
class GFG
{
    // Function to print first n numbers with two set bits
    static void printTwoSetBitNums(int n)
    {
        // Initialize higher of two sets bits
        int x = 1;
  
        // Keep reducing n for every number
        // with two set bits
        while (n > 0)
        {
            // Consider all lower set bits for
            // current higher set bit
            int y = 0;
            while (y < x)
            {
                // Print current number
                System.out.print(((1 << x) + (1 << y)) +" ");
  
                // If we have found n numbers
                n--;
                if (n == 0)
                    return;
  
                // Consider next lower bit for current
                // higher bit.
                y++;
            }
  
            // Increment higher set bit
            x++;
        }
    }
     
    // Driver program
    public static void main (String[] args)
    {
        int n = 4;
        printTwoSetBitNums(n);
    }
}
 
// This code is contributed by Pramod Kumar

Python3

# Python3 program to print first n
# numbers with exactly two set bits
 
# Prints first n numbers
# with two set bits
def printTwoSetBitNums(n) :
 
    # Initialize higher of
    # two sets bits
    x = 1
 
    # Keep reducing n for every
    # number with two set bits.
    while (n > 0) :
     
        # Consider all lower set bits
        # for current higher set bit
        y = 0
        while (y < x) :
         
            # Print current number
            print((1 << x) + (1 << y),
                          end = " " )
 
            # If we have found n numbers
            n -= 1
            if (n == 0) :
                return
 
            # Consider next lower bit
            # for current higher bit.
            y += 1
         
        # Increment higher set bit
        x += 1
     
# Driver code
printTwoSetBitNums(4)
 
# This code is contributed
# by Smitha

C#

// C# program to print first n numbers
// with exactly two set bits
using System;
 
class GFG
    {
         
    // Function to print first n
    // numbers with two set bits
    static void printTwoSetBitNums(int n)
    {
         
        // Initialize higher of
        // two sets bits
        int x = 1;
   
        // Keep reducing n for every
        // number with two set bits
        while (n > 0)
        {
             
            // Consider all lower set bits
            // for current higher set bit
            int y = 0;
            while (y < x)
            {
                 
                // Print current number
                Console.Write(((1 << x) +
                                (1 << y)) +" ");
   
                // If we have found n numbers
                n--;
                if (n == 0)
                    return;
   
                // Consider next lower bit
                // for current higher bit.
                y++;
            }
   
            // Increment higher set bit
            x++;
        }
    }
      
    // Driver program
    public static void Main()
    {
        int n = 4;
        printTwoSetBitNums(n);
    }
}
  
// This code is contributed by Anant Agarwal.

PHP

<?php
// PHP program to print
// first n numbers with
// exactly two set bits
 
// Prints first n numbers
// with two set bits
function printTwoSetBitNums($n)
{
    // Initialize higher of
    // two sets bits
    $x = 1;
 
    // Keep reducing n for
    // every number with
    // two set bits.
    while ($n > 0)
    {
        // Consider all lower set
        // bits for current higher
        // set bit
        $y = 0;
        while ($y < $x)
        {
            // Print current number
            echo (1 << $x) + (1 << $y), " ";
 
            // If we have found n numbers
            $n--;
            if ($n == 0)
                return;
 
            // Consider next lower
            // bit for current
            // higher bit.
            $y++;
        }
 
        // Increment higher set bit
        $x++;
    }
}
 
// Driver code
printTwoSetBitNums(4);
 
// This code is contributed by Ajit
?>

Javascript

<script>
 
// Javascript program to print first n numbers
// with exactly two set bits
 
// Prints first n numbers with two set bits
function printTwoSetBitNums(n)
{
 
    // Initialize higher of two sets bits
    let x = 1;
 
    // Keep reducing n for every number
    // with two set bits.
    while (n > 0)
    {
     
        // Consider all lower set bits for
        // current higher set bit
        let y = 0;
        while (y < x)
        {
         
            // Print current number
            document.write((1 << x) + (1 << y) + " ");
 
            // If we have found n numbers
            n--;
            if (n == 0)
                return;
 
            // Consider next lower bit for current
            // higher bit.
            y++;
        }
 
        // Increment higher set bit
        x++;
    }
}
 
// Driver code
printTwoSetBitNums(4);
 
// This code is contributed by Mayank Tyagi
</script>

Producción : 
 

3 5 6 9

Complejidad de tiempo : O(n)

Espacio auxiliar: O(1)
Este artículo es una contribución de Bharath Reddy Appareddy . 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 review-team@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.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *