How to print the first n numbers with exactly two set bits

Problem statement

if we are given n numbers, how can we visualize these numbers in binary forms?

A set bit is a bit that is written as "1" in the binary form of a number. For example, numbers with exactly three set bits will look like 0111, 1110, 1011, 1101, etc.

Conditions

The condition for the numbers we want to print is that there must be exactly two digits in their respective binary form. For example, binary numbers 3, 5, and 6 are written as 11, 101, and 110, respectively. These numbers have exactly two sets of bits. And numbers like 1, 2, 4, etc., do not satisfy this condition because, in binary, they are written as 01, 10, and 100, respectively.

So we only need to print those numbers that satisfy the conditions above. We'll have an entry to determine the total number of such numbers we want to print.

For example, if we pass n = 4, the output would be:

The integer 10 is not part of the output. However, it satisfies the conditions of the given problem. Because the entries (the limit on the total number of integers to be printed) are chosen to be four.

Solutions

We can consider two solutions for this problem:

Naive approach

A naive approach is to take into consideration only those numbers whose binary form starts with 1. Then we can check if another "1" exists in the binary representation of the number. For example, the number 5 in binary is 101. It starts with 1, so we have our first required set bit. Then we'll check for another set bit and print it.

We might get the required result, but this is not a desirable approach.

Efficient approach

In this approach, we can consider the fact that numbers in their binary forms are simply powers of two, changing based on the set bits as they go higher. For example, $2^1=001$ , $2^2=010$ , $2^3=100$ and so on.

So, we can first initialize the higher of the two set bits (power of 2) and then take into consideration the lower set bits for the current higher set bit while decrementing n for all the required numbers, we find exactly two set bits.

Code example

Let's look at the code in C++ and Python3:

#include <iostream>
using namespace std;
 
void getTwoSetNumbers(int n) //defining the function
{
    int number = 1; //the counter of the number being printed
    int higher = 1; //the higher set bit declared
    cout << "The required numbers are:" << endl;
    while (n > 0) 
    //while we do not reach the required limit of numbers to be printed
    {
        int lower = 0; //the lower set bit declared
      
        while (lower < higher) 
        //until all lower set bit numbers below the higher set bit are not printed
        {
            n--; //decrementing n
            cout << "Number " << number << " =>  ";
            int output = (1 << higher) + (1 << lower); //converting the bits into the required number
            number++;
            lower++; //incrementing the lower set bit to the next number to be printed
            
            cout << output << " " << endl;
            if (n == 0) //if the limit of the numbers to be printed is reached
                break;
 
            
        }
        higher++; //incrementing to the next higher set bit
        
        if (n == 0)
          break;
      
    }
}
 
int main() 
{
    getTwoSetNumbers(6); //function call for n = 6
 
    return 0;
}

Code explanation

In the code provided above, the variable higher specifies the higher set bit and the variable lower is the lower set bit, which keeps on incrementing until its value gets greater than higher , while the numbers with exactly two set bits get printed. For the algorithm to stop, the limit n provided by the user will keep on decrementing until it reaches zero.

The variable, output has been specified to store the number to be printed by combining the values of the lower and higher set bits, added by 1.

Once n = 0, the loops break/function returns, and the numbers stop printing.

Time complexity

The time complexity for the algorithm above is $O(n)$ .

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments