Dado un número N, imprima todos los números que son un conjunto AND bit a bit de la representación binaria de N. El conjunto AND bit a bit de un número N son todos los números posibles x menores o iguales a N tales que N & i es igual a x para algún número i.
Ejemplos:
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
Enfoque simple : un enfoque ingenuo es iterar desde todos los números de 0 a N y verificar si (N & i == i). Imprime los números que cumplen la condición especificada.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to print all bitwise
// subsets of N (Naive approach)
#include <bits/stdc++.h>
using namespace std;
// function to find bitwise subsets
// Naive approach
void printSubsets(int n) {
for (int i = 0; i <= n; i++)
if ((n & i) == i)
cout << i << " ";
}
// Driver Code
int main() {
int n = 9;
printSubsets(n);
return 0;
}
Java
// JAVA program to print all bitwise
// subsets of N (Naive approach)
class GFG {
// function to find bitwise subsets
// Naive approach
static void printSubsets(int n)
{
for (int i = 0; i <= n; i++)
if ((n & i) == i)
System.out.print(i + " ");
}
// Driver function
public static void main(String[] args)
{
int n = 9;
printSubsets(n);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to print all bitwise # subsets of N (Naive approach) def printSubsets(n): for i in range(n + 1): if ((n & i) == i): print(i ," ", end = "") # Driver code n = 9 printSubsets(n) # This code is contributed by Anant Agarwal.
C#
// C# program to print all bitwise
// subsets of N (Naive approach)
using System;
class GFG {
// function to find bitwise subsets
// Naive approach
static void printSubsets(int n)
{
for (int i = 0; i <= n; i++)
if ((n & i) == i)
Console.Write(i + " ");
}
// Driver function
public static void Main()
{
int n = 9;
printSubsets(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to print all bitwise
// subsets of N (Naive approach)
// function to find bitwise subsets
// Naive approach
function printSubsets($n)
{
for ($i = 0; $i <= $n; $i++)
if (($n & $i) == $i)
echo $i." ";
}
// Driver Code
$n = 9;
printSubsets($n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program to print all bitwise
// subsets of N (Efficient approach)
// function to find bitwise
// subsets Efficient approach
function printSubsets(n)
{
for (let i = n; i > 0; i = (i - 1) & n)
document.write(i + " ");
document.write(" 0 ");
}
// Driver code
let n = 9;
printSubsets(n);
// This code is contributed by souravghosh0416.
</script>
Producción :
0 1 8 9
Complejidad de tiempo : O(N)
Solución eficiente : una solución eficiente es usar operadores bit a bit para encontrar los subconjuntos. En lugar de iterar para cada i, podemos simplemente iterar solo para los subconjuntos bit a bit. Iterando hacia atrás para i=(i-1)&n nos da cada subconjunto bit a bit, donde i comienza desde n y termina en 1.
A continuación se muestra la implementación de la idea anterior:
C++
// CPP program to print all bitwise
// subsets of N (Efficient approach)
#include <bits/stdc++.h>
using namespace std;
// function to find bitwise subsets
// Efficient approach
void printSubsets(int n) {
for (int i = n; i > 0; i = (i - 1) & n)
cout << i << " ";
cout << 0;
}
// Driver Code
int main() {
int n = 9;
printSubsets(n);
return 0;
}
Java
// Java program to print all bitwise
// subsets of N (Efficient approach)
class GFG
{
// function to find bitwise
// subsets Efficient approach
static void printSubsets(int n)
{
for (int i = n; i > 0; i = (i - 1) & n)
System.out.print(i + " ");
System.out.print(" 0 ");
}
// Driver Code
public static void main(String[] args)
{
int n = 9;
printSubsets(n);
}
}
// This code is contributed by ajit.
Python3
# Python 3 program to
# print all bitwise
# subsets of N
# (Efficient approach)
# function to find
# bitwise subsets
# Efficient approach
def printSubsets(n):
i=n
while(i != 0):
print(i,end=" ")
i=(i - 1) & n
print("0")
# Driver Code
n = 9
printSubsets(n)
# This code is contributed by
# Smith Dinesh Semwal
C#
// C# program to print all bitwise
// subsets of N (Efficient approach)
using System;
public class GFG {
// function to find bitwise subsets
// Efficient approach
static void printSubsets(int n) {
for (int i = n; i > 0; i = (i - 1) & n)
Console.Write(i +" ");
Console.WriteLine("0");
}
// Driver Code
static public void Main () {
int n = 9;
printSubsets(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to print all bitwise
// subsets of N (Efficient approach)
// function to find bitwise subsets
// Efficient approach
function printSubsets($n)
{
for ($i = $n; $i > 0;
$i = ($i - 1) & $n)
echo $i." ";
echo "0";
}
// Driver Code
$n = 9;
printSubsets($n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to print all bitwise
// subsets of N (Efficient approach)
// Function to find bitwise subsets
// Efficient approach
function printSubsets(n)
{
for(let i = n; i > 0; i = (i - 1) & n)
document.write(i +" ");
document.write("0" + "</br>");
}
// Driver code
let n = 9;
printSubsets(n);
// This code is contributed by divyesh072019
</script>
Producción :
9 8 1 0
Complejidad de tiempo : O(K), donde K es el número de subconjuntos bit a bit de N.