Print first n numbers with exactly two set bits - GeeksforGeeks

Print first n numbers with exactly two set bits - GeeksforGeeks
Given a number n, print first n positive integers with exactly two set bits in their binary representation.

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.

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++;

    }

}

Read full article from Print first n numbers with exactly two set bits - GeeksforGeeks