原文:
给定一个整数 n ，任务是打印由存在于 n 的二进制表示中的
示例:
输入: n = 5 输出: 5 4 1 说明: n 的二进制表示为“101”，因此所有需要的子集为{“101”、“100”、“001”、“000”}。
输入: n = 25 输出: 25 24 17 16 9 8 1 说明: n 的二进制表示为“1101”。因此，所有必需的子集都是{“11001”、“11000”、“10001”、“10000”、“01001”、“01000”、“0001”、“0000”}。
简单方法:最简单的方法是遍历范围内的每个掩码【t20，1】<<(n)中的设置位计数，并检查除了 n 中的位之外，是否没有其他位设置在其中。然后，打印出来。 时间复杂度:o(2(n 中设置位计数) ) 辅助空间:* o(1)*
*高效方法:*上述方法可以通过仅遍历作为掩码 n 的子集的子库来优化。
let *s be the current sub-mask, which is a subset of the mask n . then, it can be observed that by assigning s = (s–1) & n , the next subtask of n less than s can be obtained. in [t0】 s-1 【t1 , it flips all the bits to the right of the rightmost setting bit, including the rightmost setting bit of s . therefore, after performing bit by bit & with n , the subtasks of n are obtained. therefore, s = (s–1) & n gives the next subtask of n , which is less than s .*
按照以下步骤解决问题:
- 初始化一个变量，比如 s = n.****
- 在 s > 0 时迭代，在每次迭代中，打印 s 的值。
- 分配s =(s–1)&n .****
下面是上述方法的实现:
c
// c program for above approach
#include
using namespace std;
// function to print the submasks of n
void submasks(int n)
{
for (int s = n; s; s = (s - 1) & n) {
cout << s << " ";
}
}
// driver code
int main()
{
int n = 25;
submasks(n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for above approach
import java.util.*;
class gfg
{
// function to print the submasks of n
static void submasks(int n)
{
for (int s = n; s > 0; s = (s - 1) & n)
{
system.out.print(s " ");
}
}
// driver code
public static void main(string args[])
{
int n = 25;
submasks(n);
}
}
// this code is contributed by surendra_gangwar.
python 3
# python3 program for the above approach
# function to print the submasks of n
def submasks(n) :
s = n
while s > 0:
print(s,end=' ')
s = (s - 1) & n
# driven code
if __name__ == '__main__':
n = 25
submasks(n)
# this code is contributed by bgangwar59.
c#
// c# program for the above approach
using system;
class gfg{
// function to print the submasks of n
static void submasks(int n)
{
for (int s = n; s > 0; s = (s - 1) & n)
{
console.write(s " ");
}
}
// driver code
static public void main()
{
int n = 25;
submasks(n);
}
}
// this code is contributed by code_hunt.
java 描述语言
**output:
25 24 17 16 9 8 1**
*时间复杂度:o(2(n 中设置位计数))t8】辅助空间: o(1)***
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
