Выведите первые n чисел ровно с двумя заданными битами

Опубликовано: 20 Января, 2022

Учитывая число n, выведите первые n натуральных чисел с ровно двумя заданными битами в их двоичном представлении.
Примеры :

 Ввод: n = 3
Вывод: 3 5 6
Первые 3 числа с двумя установленными битами - 3 (0011),
5 (0101) и 6 (0110)

Ввод: n = 5
Выход: 3 5 6 9 10 12

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

A Simple Solution is to consider all positive integers one by one starting from 1. For every number, check if it has exactly two sets bits. If a number has exactly two set bits, print it and increment count of such numbers.
An Efficient Solution is to directly generate such numbers. If we clearly observe the numbers, we can rewrite them as given below 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), ………
All numbers can be generated in increasing order according to higher of two set bits. The idea is to fix higher of two bits one by one. For current higher set bit, consider all lower bits and print the formed numbers.
 

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>

Выход :

 3 5 6 9

Сложность времени: O (n)
Эта статья предоставлена Bharath Reddy Appareddy . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ