ABC 269 C - Submask(dfs+位运算)

C - Submask(dfs+位运算)

题目大意:
给定一个十进制的数字，让我们求出它的二进制下的1可以改变时候的数字

Sample Input 1 
11
Sample Output 1 
0
1
2
3
8
9
10
11
The binary representation of N=11 (10)==1011 (2).
The non-negative integers x that satisfy the condition are:
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)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=200200,M=2002;
LL n;
set<LL> s;
void dfs(LL u,LL ans)
{
    if(u==-1)//寻找完了60位
    {
        //cout<<ans<<endl;
        s.insert(ans);
        return ;
    }
    if(n>>u&1)//向右移动的位数，如果这一位是1的话，就可以有0和1两种选择
    {
        dfs(u-1,ans*2);
        dfs(u-1,ans*2+1);
    }
    else dfs(u-1,ans*2);//如果当前位置是0，直接当前位置变大2倍数
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n;
        dfs(60,0);//从最低位从右往左寻找，初始化为0
        for(auto i:s)
            cout<<i<<endl;
    }
    return 0;
}