#ABC269C. 子掩码

子掩码

AT_abc269_c [ABC269C] Submask

题目描述

\hspace{15pt}给定一个非负整数 nn,请按升序输出所有满足以下条件的非负整数 xx:

∙ \hspace{23pt}\bullet\,将 xx 用二进制表示时,其所有为 11 的位的集合,必须是 nn 的二进制表示中为 11 的位的集合的子集;

∙ \hspace{23pt}\bullet\,换句话说,对于所有非负整数 kk,如果 xx 的二进制表示中权值为 2k2^k 的位为 11,那么 nn 的对应位也必须为 11。

输入格式

\hspace{15pt}在一行上输入一个整数 n(0≦n<260)n \left(0 \leqq n < 2^{60}\right)。保证 nn 的二进制表示中为 11 的位不超过 1515 个。

输出格式

\hspace{15pt}输出若干行,每行一个十进制整数,按升序给出所有满足条件的非负整数 xx。

测试样例

11
0
1
2
3
8
9
10
11

样例 1 解释

\hspace{15pt}将 n=11(10)n=11_{(10)} 用二进制表示为 1011(2)1011_{(2)},其中为 11 的位分别是权值为 20,21,232^0,2^1,2^3 的位。满足条件的非负整数 xx 如下:

∙ \hspace{23pt}\bullet\,0000(2)=0(10)0000_{(2)}=0_{(10)}

∙ \hspace{23pt}\bullet\,0001(2)=1(10)0001_{(2)}=1_{(10)}

∙ \hspace{23pt}\bullet\,0010(2)=2(10)0010_{(2)}=2_{(10)}

∙ \hspace{23pt}\bullet\,0011(2)=3(10)0011_{(2)}=3_{(10)}

∙ \hspace{23pt}\bullet\,1000(2)=8(10)1000_{(2)}=8_{(10)}

∙ \hspace{23pt}\bullet\,1001(2)=9(10)1001_{(2)}=9_{(10)}

∙ \hspace{23pt}\bullet\,1010(2)=10(10)1010_{(2)}=10_{(10)}

∙ \hspace{23pt}\bullet\,1011(2)=11(10)1011_{(2)}=11_{(10)}

0
0
576461302059761664
0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

数据范围与提示

\hspace{15pt}输入可能超出 3232 位有符号整数的范围。