C++:左シフト演算子、bit全探索メモ

bit 全探索の書き方はわかったけど左シフト演算子 (1<<n) みたいなやつがよくわからなかったので調べた。

#include <bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  cout << (0<<n) << endl;
  cout << (1<<n) << endl;
  cout << (2<<n) << endl;
  cout << (3<<n) << endl;
  cout << (4<<n) << endl;
}

n に2を入れたときの出力

0
4
8
12
16

二進数で考えてみる。
0 は 0
1 は 1
2 は 10
3 は 11
4 は 100
これにそれぞれ n 個 0 を加えてみる。今回は 2 個
0 は 000
1 は 100
2 は 1000
3 は 1100
4 は 10000
これを10進数に戻すと
000 = 0 + 0 + 0 = 0
100 = 4 + 0 + 0 = 4
1000 = 8 + 0 + 0 + 0 = 8
1100 = 8 + 4 + 0 + 0 = 12
10000 = 16 + 0 + 0 + 0 + 0 = 16

(1<<n) が 2^n乗になるのは1をnビット左にシフトしたから。

bit 全探索をしたときに思ったのは nCr も求められそうということ。
ただ問題として bit 全探索の限界は n が 20 くらいまでだそうなのであんまり大きすぎるのは無理。

#include <bits/stdc++.h>

using namespace std;

int main(){
  int n,r;
  cin >> n >> r;
  int count = 0;
  for(int b=0;b<(1<<n);b++){
    vector<int> vs;
    for(int i=0;i<n;i++){
      if(b & (1<<i)){
        vs.push_back(i);
      }
    }
    if((int)vs.size() == r){
      for(int i=0;i<r;i++){
        cout << vs[i];
        if(i<r-1){
          cout << ",";
        }
      }
      count++;
      cout << endl;
    }
  }
  cout << count;
}

n に 7, r に 5 を入れた時の出力。

0,1,2,3,4
0,1,2,3,5
0,1,2,4,5
0,1,3,4,5
0,2,3,4,5
1,2,3,4,5
0,1,2,3,6
0,1,2,4,6
0,1,3,4,6
0,2,3,4,6
1,2,3,4,6
0,1,2,5,6
0,1,3,5,6
0,2,3,5,6
1,2,3,5,6
0,1,4,5,6
0,2,4,5,6
1,2,4,5,6
0,3,4,5,6
1,3,4,5,6
2,3,4,5,6
21

最後の 21 は条件に当てはまる個数