Print bitwise AND set of a number N in C++

In this problem, we have to print all the numbers from 0 to n which are Bitwise AND of a binary of n.

Let’s take an example to understand the concept better.

Input : N = 4. Output : 0 4 Explanation :    0 & 4 = 0    1 & 4 = 0    2 & 4 = 0    3 & 4 = 0    4 & 4 = 4. Input : N = 6 Output : 0, 2, 4, 6

To solve this problem, we need to use bitwise operators. Using these we will find the required subsets. We will iterate backward from n to 1 using a different update function that will use only those values that return are outputs of and operation of some AND with n. The operation would be i = (i-1) & N.

Based on this idea lets create an algorithm −

Algorithm

Step 1 : Loop from n to 1 using decrement operator i = (i-1) & n Step 2 : PRINT i. Step 3 : EXIT.

Example

Program implementation of the above algorithm −

 Live Demo

#include <iostream> using namespace std; int main() {    int n = 11;    for (int i = n; i > 0; i = (i - 1) & n)       cout << i << " ";    cout << 0;    return 0; }

Output

11 10 9 8 3 2 1 0