Given a number N, print all the numbers which are a bitwise AND set of the binary representation of N. Bitwise AND set of a number N is all possible numbers x smaller than or equal N such that N & i is equal to x for some number i.
Examples :
Input : N = 5
Output : 0, 1, 4, 5
Explanation: 0 & 5 = 0
1 & 5 = 1
2 & 5 = 0
3 & 5 = 1
4 & 5 = 4
5 & 5 = 5
So we get 0, 1, 4 and 5 in the
bitwise subsets of N.
Input : N = 9
Output : 0, 1, 8, 9
Simple Approach: A naive approach is to iterate from all numbers from 0 to N and check if (N&i == i). Print the numbers which satisfy the specified condition.
Below is the implementation of above idea:
C++
#include <bits/stdc++.h>
using namespace std;
void printSubsets(int n) {
for (int i = 0; i <= n; i++)
if ((n & i) == i)
cout << i << " ";
}
int main() {
int n = 9;
printSubsets(n);
return 0;
}
|
Java
class GFG {
static void printSubsets(int n)
{
for (int i = 0; i <= n; i++)
if ((n & i) == i)
System.out.print(i + " ");
}
public static void main(String[] args)
{
int n = 9;
printSubsets(n);
}
}
|
Python3
def printSubsets(n):
for i in range(n + 1):
if ((n & i) == i):
print(i ," ", end = "")
n = 9
printSubsets(n)
|
C#
using System;
class GFG {
static void printSubsets(int n)
{
for (int i = 0; i <= n; i++)
if ((n & i) == i)
Console.Write(i + " ");
}
public static void Main()
{
int n = 9;
printSubsets(n);
}
}
|
Javascript
<script>
function printSubsets(n)
{
for (let i = n; i > 0; i = (i - 1) & n)
document.write(i + " ");
document.write(" 0 ");
}
let n = 9;
printSubsets(n);
</script>
|
PHP
<?php
function printSubsets($n)
{
for ($i = 0; $i <= $n; $i++)
if (($n & $i) == $i)
echo $i." ";
}
$n = 9;
printSubsets($n);
?>
|
Time Complexity : O(N)
Efficient Solution: An efficient solution is to use bitwise operators to find the subsets. Instead of iterating for every i, we can simply iterate for the bitwise subsets only. Iterating backward for i=(i-1)&n gives us every bitwise subset, where i starts from n and ends at 1.
Below is the implementation of above idea:
C++
#include <bits/stdc++.h>
using namespace std;
void printSubsets(int n) {
for (int i = n; i > 0; i = (i - 1) & n)
cout << i << " ";
cout << 0;
}
int main() {
int n = 9;
printSubsets(n);
return 0;
}
|
Java
class GFG
{
static void printSubsets(int n)
{
for (int i = n; i > 0; i = (i - 1) & n)
System.out.print(i + " ");
System.out.print(" 0 ");
}
public static void main(String[] args)
{
int n = 9;
printSubsets(n);
}
}
|
Python3
def printSubsets(n):
i=n
while(i != 0):
print(i,end=" ")
i=(i - 1) & n
print("0")
n = 9
printSubsets(n)
|
C#
using System;
public class GFG {
static void printSubsets(int n) {
for (int i = n; i > 0; i = (i - 1) & n)
Console.Write(i +" ");
Console.WriteLine("0");
}
static public void Main () {
int n = 9;
printSubsets(n);
}
}
|
Javascript
<script>
function printSubsets(n)
{
for(let i = n; i > 0; i = (i - 1) & n)
document.write(i +" ");
document.write("0" + "</br>");
}
let n = 9;
printSubsets(n);
</script>
|
PHP
<?php
function printSubsets($n)
{
for ($i = $n; $i > 0;
$i = ($i - 1) & $n)
echo $i." ";
echo "0";
}
$n = 9;
printSubsets($n);
?>
|
Output :
9 8 1 0
Time Complexity: O(K), where K is the number of bitwise subsets of N.
Approach: Optimized Bit Manipulation
Steps:
- Initialize an empty list res with 0 as the first element.
- Initialize a variable x as 1.
- While x is less than or equal to N, do the following:
a. If the x-th bit of N is 1, then for each element r in res, append r | x to res.
b. Multiply x by 2.
- Return the final list res.
C++
#include <iostream>
#include <vector>
using namespace std;
vector<int> bitwise_and_set(int N) {
vector<int> res = {0};
int x = 1;
while (x <= N) {
if (N & x) {
vector<int> temp;
for (int r : res) {
temp.push_back(r | x);
}
res.insert(res.end(), temp.begin(), temp.end());
}
x <<= 1;
}
return res;
}
int main() {
int N = 5;
vector<int> result = bitwise_and_set(N);
for (int r : result) {
cout << r << " ";
}
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.List;
public class Main {
public static List<Integer> bitwiseAndSet(int N) {
List<Integer> res = new ArrayList<>();
res.add(0);
int x = 1;
while (x <= N) {
if ((N & x) != 0) {
List<Integer> temp = new ArrayList<>();
for (int r : res) {
temp.add(r | x);
}
res.addAll(temp);
}
x <<= 1;
}
return res;
}
public static void main(String[] args) {
int N = 5;
List<Integer> result = bitwiseAndSet(N);
for (int r : result) {
System.out.print(r + " ");
}
}
}
|
Python3
def bitwise_and_set(N):
res = [0]
x = 1
while x <= N:
if N & x:
res += [r | x for r in res]
x <<= 1
return res
N = 5
print(bitwise_and_set(N))
|
C#
using System;
using System.Collections.Generic;
public class Program {
public static List<int> BitwiseAndSet(int N) {
List<int> res = new List<int> {0};
int x = 1;
while (x <= N) {
if ((N & x) != 0) {
List<int> temp = new List<int>();
foreach (int r in res) {
temp.Add(r | x);
}
res.AddRange(temp);
}
x <<= 1;
}
return res;
}
public static void Main() {
int N = 5;
List<int> result = BitwiseAndSet(N);
foreach (int r in result) {
Console.Write(r + " ");
}
}
}
|
Javascript
function bitwiseAndSet(N) {
var res = [0];
var x = 1;
while (x <= N) {
if (N & x) {
var temp = [];
for (var r of res) {
temp.push(r | x);
}
res = res.concat(temp);
}
x <<= 1;
}
return res;
}
var N = 5;
var result = bitwiseAndSet(N);
for (var r of result) {
console.log(r + " ");
}
|
Time Complexity: O(log N)
Auxiliary Space: O(2^log N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
