Official

C - Submask Editorial by en_translator


In this editorial, we call the \(2^k\)s place when written base \(2\)\(k\)-th bit.”

Solution 1. Expand the set step-by-step

By performing the following steps, we can construct the answer:

  • First, let \(S=\{0\}\).
  • While \(i=0,1,\dots,59\), repeat the following:
    • If the \(i\)-th bit of \(N\) is \(1\), update as follows:
      • For all element \(x\) in \(S\), simultaneously add a new element \(y\) where the \(i\)-th bit of \(x\) is set to \(1\).

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long x;
  cin >> x;
  vector<long long> res={0};
  for(int d=0;d<60;d++){
    if(x&(1ll<<d)){
      int sz=res.size();
      for(int i=0;i<sz;i++){
        res.push_back(res[i]|(1ll<<d));
      }
    }
  }
  sort(res.begin(),res.end());
  for(auto &nx : res){cout << nx << "\n";}
  return 0;
}

Bonus: This code is still AC (accepted) if the \(17\)-th line (sort) is removed. Why is that?

Solution 2. Construct in a bit exhaustive search

First, enumerate which bit is set in \(N\). (Let \(A=(A_1,A_2,\dots,A_k)\) be the sequence of indices of such bits.)
Then, iterate integer \(i\) from \(0\) through \(2^k-1\), where \(k\) is the number of the bit set.
We can obtain the desired set by setting the \(A_j\)-bit if the \(j\)-th bit of \(i\) is set.
Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long n;
  cin >> n;
  vector<int> a;
  for(int i=0;i<60;i++){
    if(n&(1ll<<i)){a.push_back(i);}
  }
  int k=a.size();
  vector<long long> res;
  for(int i=0;i<(1<<k);i++){
    long long cur=0;
    for(int j=0;j<k;j++){
      if(i&(1<<j)){cur|=(1ll<<a[j]);}
    }
    res.push_back(cur);
  }
  sort(res.begin(),res.end());
  for(auto &nx : res){cout << nx << "\n";}
  return 0;
}

Bonus: This code is still AC if the \(21\)-th line (sort) is removed. Why is that?

Solution 3: Clever loop

Considering this problem as a problem of treating bit sequences as a sets, we can see this problem as iterating all the subset of a set. The loop in the sample code is a way to get AC for this problem.
(Note that you need to reverse the answer because the subsets are iterating in descending order.)
In the following Japanese article, some other techniques are also introduced.
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 (“Expressing subsets with a bit sequence (Bit operation technique Advent Calendar 2016 Day 1)”)
Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  long long x;
  cin >> x;
  vector<long long> res;
  for(long long i=(1ll<<60)-1; i>=0; i--){
    i&=x;
    res.push_back(i);
  }
  reverse(res.begin(),res.end());
  for(auto &nx : res){cout << nx << "\n";}
  return 0;
}

posted:
last update: