Bitwise Operators: Print the numbers without consecutive 1s in binary representation

Problem Statement:

You are given a number “N”.

You need to print all the numbers with no consecutive 1s in binary representation from 1 to N bit.

Example:

Input N = 4

Output:

1 2 4 5 8 9 10

For all the numbers above, there is no consecutive ones in their binary representation.

Solution Explanation:

For a value n, there will be 2^n combinations.

Iterate through all 2^n numbers and check if consecutive bits are set or not.

For that, do bitwise and of current number i and left shift i.

If the bitwise and contains non zero bit, then the given number has consecutive set bits.

Code Solution

#include<iostream>
using namespace std;

void solution(int n)
{
    // calculate 2^n number
	int val = (1 << n);

    // loop through 1 to 2 power n
	for (int i = 1; i < val; i++)
	{
        // check if the number does not have
        // consecutive 1's and print it
		if ((i & (i << 1)) == 0)
			cout << i << " ";
	}
}

int main()
{
	int n = 4;
	solution(n);
	return 0;
}

Output

1 2 4 5 8 9 10