A6465. 子集枚举
编程题
普及/提高-
知识点
题目描述
给定一个非负整数 $N$。请按从小到大的顺序输出所有满足以下条件的非负整数 $x$。
* 将 $x$ 和 $N$ 写成二进制表示时，$x$ 中为 $1$ 的那些二进制位（位置）的集合，必须是 $N$ 中为 $1$ 的那些二进制位（位置）的集合的子集。
* 也就是说，对任意非负整数 $k$，如果 $x$ 在 $2^k$ 位上的数字是 $1$，那么 $N$ 在 $2^k$ 位上的数字也必须是 $1$。
### 数据范围
- $N$ 是整数。
- $0 \le N < 2^{60}$
- 在 $N$ 的二进制表示中，最多有 $15$ 个数位包含 $1$ 。
* 将 $x$ 和 $N$ 写成二进制表示时，$x$ 中为 $1$ 的那些二进制位（位置）的集合，必须是 $N$ 中为 $1$ 的那些二进制位（位置）的集合的子集。
* 也就是说，对任意非负整数 $k$，如果 $x$ 在 $2^k$ 位上的数字是 $1$，那么 $N$ 在 $2^k$ 位上的数字也必须是 $1$。
### 数据范围
- $N$ 是整数。
- $0 \le N < 2^{60}$
- 在 $N$ 的二进制表示中，最多有 $15$ 个数位包含 $1$ 。
输入格式
输入内容由标准输入法提供，格式如下
$N$
$N$
输出格式
将答案按升序打印为十进制整数，每行一个。
输入输出样例
输入 #1
11
输出 #1
0 1 2 3 8 9 10 11
输入 #2
0
输出 #2
0
输入 #3
576461302059761664
输出 #3
0 524288 549755813888 549756338176 576460752303423488 576460752303947776 576461302059237376 576461302059761664
说明/提示
### 样例一解释：
$N = 11_{(10)}$ 的二进制表示为 $1011_{(2)}$ 。
满足条件的非负整数 $x$ 是：
- $0000_{(2)}=0_{(10)}$
- $0001_{(2)}=1_{(10)}$
- $0010_{(2)}=2_{(10)}$
- $0011_{(2)}=3_{(10)}$
- $1000_{(2)}=8_{(10)}$
- $1001_{(2)}=9_{(10)}$
- $1010_{(2)}=10_{(10)}$
- $1011_{(2)}=11_{(10)}$
输入可能不适合32 位有符号整数。
$N = 11_{(10)}$ 的二进制表示为 $1011_{(2)}$ 。
满足条件的非负整数 $x$ 是：
- $0000_{(2)}=0_{(10)}$
- $0001_{(2)}=1_{(10)}$
- $0010_{(2)}=2_{(10)}$
- $0011_{(2)}=3_{(10)}$
- $1000_{(2)}=8_{(10)}$
- $1001_{(2)}=9_{(10)}$
- $1010_{(2)}=10_{(10)}$
- $1011_{(2)}=11_{(10)}$
输入可能不适合32 位有符号整数。