プログラミング学習記録【18日目】/ビット演算

3.05.ビット演算

0と1の2通りで状態を表現できるデータの単位をビットト呼ぶ。
ビットをいくつか並べたものをビット列と呼び、ビット列に関する演算をビット演算と呼ぶ。
今回は以下の6つについて考える。
･AND演算
･OR演算
･XOR演算
･NOT演算
･左シフト演算
･右シフト演算

AND演算(論理積)
対応するビットがともに1の場合のみ解が1となり、それ以外は0となる演算。

OR演算
対応するビットの少なくとも一方が1の場合、結果が1となる演算。
ともに0のときのみ、結果が0となる。

XOR演算
対応するビットが同じ場合のみ、結果が0となる。
どちらか一方が1のときのみ、結果が1となる。

NOT演算
与えられたビットを反転する演算。
1が与えられれば0を返し、0が与えられれば1を返す。

左シフト演算
ビットを指定された分左向きにずらす操作をする演算。
もとのビット数と同じビット列となり、はみ出した分は切り捨てられ、足りない分は0で埋められる。

右シフト演算。
ビットを指定された分右向きにずらす操作をする演算。
もとのビット数と同じビット列となり、はみ出した分は切り捨てられ、足りない分は0で埋められる。

これらのビット演算は、集合の演算を行ったり、高速な演算が必要な場合に用いられる。
C++でビット列を扱うにはSTLのbitsetを用いる。

bitset<ビット数> 変数名;
bitset<ビット数> 変数名("ビット列");
// ex) bitset<4> b("1010");

bitsetでのビット演算子は以下の記号で対応している。

･AND演算 &
･OR演算 |
･XOR演算 ^
･NOT演算 ~
･左シフト演算 <<
･右シフト演算 >>

bitsetにはビット列を扱う際に便利な関数が用意されている。

変数.set(位置, 値); // 0で始まるインデックスで位置を指定する。 値は0･1のどちらか
変数.test(調べる位置); // 0で始まるインデックスで位置を指定する。 ビットが1ならtrueを、ビットが0ならfalseを返す。

EX25.集合の操作

集合A,Bに対して操作を行う関数を実装したプログラムを作る。
実装する関数は以下の通り。

intersection // AとBに共通して含まれる要素の集合を返す
union_set // AとBの少なくとも一方に含まれる要素の集合を返す
symmetric_diff // A,Bのうち一方にだけ含まれる要素の集合を返す
subtract x // Aから値xを削除する
increment // Aに含まれる要素すべてに1を加える。49は操作後0になるものとする。
decrement // Aに含まれる要素すべてから1を引く。0は操作後49になるものとする。

プログラムの雛形は以下の通り。

   #include <bits/stdc++.h>
   using namespace std;
    
   // 各操作を行う関数を実装する
    
   // AとBに共通して含まれる要素からなる集合を返す
   bitset<50> intersection(bitset<50> A, bitset<50> B) {
   }
   // AとBのうち少なくとも一方に含まれる要素からなる集合を返す
   bitset<50> union_set(bitset<50> A, bitset<50> B) {
   }
   // AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す
   bitset<50> symmetric_diff(bitset<50> A, bitset<50> B) {
   }
   // Aから値xを除く
   bitset<50> subtract(bitset<50> A, int x) {
   }
   // Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする)
   bitset<50> increment(bitset<50> A) {
   }
   // Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする)
   bitset<50> decrement(bitset<50> A) {
   }
    
   // Sに値xを加える
   bitset<50> add(bitset<50> S, int x) {
     S.set(x, 1);  // xビット目を1にする
     return S;
   }
    
   // 集合Sの内容を昇順で出力する(スペース区切りで各要素の値を出力する)
   void print_set(bitset<50> S) {
     vector<int> cont;
     for (int i = 0; i < 50; i++) {
       if (S.test(i)) {
         cont.push_back(i);
       }
     }
     for (int i = 0; i < cont.size(); i++) {
       if (i > 0) cout << " ";
       cout << cont.at(i);
     }
     cout << endl;
   }
    
   // これより下は書き換えない
    
   int main() {
     bitset<50> A, B;
     int N;
     cin >> N;
     for (int i = 0; i < N; i++) {
       int x;
       cin >> x;
       A = add(A, x);
     }
     int M;
     cin >> M;
     for (int i = 0; i < M; i++) {
       int x;
       cin >> x;
       B = add(B, x);
     }
    
     // 操作
     string com;
     cin >> com;
    
     if (com == "intersection") {
       print_set(intersection(A, B));
     } else if (com == "union_set") {
       print_set(union_set(A, B));
     } else if (com == "symmetric_diff") {
       print_set(symmetric_diff(A, B));
     } else if (com == "subtract") {
       int x;
       cin >> x;
       print_set(subtract(A, x));
     } else if (com == "increment") {
       print_set(increment(A));
     } else if (com == "decrement") {
       print_set(decrement(A));
     }
   }

やることは明確なので一つ一つ考えていく。
1つ目は共通して含まれる要素でできる集合を返すもの。
返り値の設定だけでいいので return ~ で ~ に計算を入れればいいだけ。
共通なら & を入れればいい。
同様に 少なくとも~ なら | 、どちらか~ なら ^ を入れれば良い。
ここまでをコードに落とし込むと以下のようになる。

// AとBに共通して含まれる要素からなる集合を返す
bitset<50> intersection(bitset<50> A, bitset<50> B)
{
 return A & B;
}
// AとBのうち少なくとも一方に含まれる要素からなる集合を返す
bitset<50> union_set(bitset<50> A, bitset<50> B)
{
 return A | B;
}
// AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す
bitset<50> symmetric_diff(bitset<50> A, bitset<50> B)
{
 return A ^ B;
}

次の値xを除くのはsetを使えばいいが、今までの単純なreturnに続く文だとコンパイル時エラーを吐いていたので、return A という形に落とし込めるようコードに落とし込む。

// Aから値xを除く
bitset<50> subtract(bitset<50> A, int x)
{
 A.set(x, 0);
 return A;
}

要素に1加えるのはめちゃくちゃ考えたが、要素は2進数で与えられるので、2進数に1足したら要素が左に1つずつずれて末尾に1追加される。ちなみに左シフトの項目を見直してやっと考えが至った。コードに落とし込むと以下のようになる。

// Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする)
bitset<50> increment(bitset<50> A)
{
 bitset<50> ans = A << 1;
 if (A.test(49))
 {
   ans.set(0, 1);
 }
 return ans;
}

1を引くのもこれの逆を行うので、以下の通り。

// Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする)
bitset<50> decrement(bitset<50> A)
{
 bitset<50> ans = A >> 1;
 if (A.test(0))
 {
   ans.set(49, 1);
 }
 return ans;
}

それから下は最初から入っていたので割愛。
コード全文は以下の通り。

#include <bits/stdc++.h>
using namespace std;

// 各操作を行う関数を実装する

// AとBに共通して含まれる要素からなる集合を返す
bitset<50> intersection(bitset<50> A, bitset<50> B)
{
 return A & B;
}
// AとBのうち少なくとも一方に含まれる要素からなる集合を返す
bitset<50> union_set(bitset<50> A, bitset<50> B)
{
 return A | B;
}
// AとBのうちどちらか一方にだけ含まれる要素からなる集合を返す
bitset<50> symmetric_diff(bitset<50> A, bitset<50> B)
{
 return A ^ B;
}
// Aから値xを除く
bitset<50> subtract(bitset<50> A, int x)
{
 A.set(x, 0);
 return A;
}
// Aに含まれる要素に1を加える(ただし、要素49が含まれる場合は0になるものとする)
bitset<50> increment(bitset<50> A)
{
 bitset<50> ans = A << 1;
 if (A.test(49))
 {
   ans.set(0, 1);
 }
 return ans;
}
// Aに含まれる要素から1を引く(ただし、要素0が含まれる場合は49になるものとする)
bitset<50> decrement(bitset<50> A)
{
 bitset<50> ans = A >> 1;
 if (A.test(0))
 {
   ans.set(49, 1);
 }
 return ans;
}

// Sに値xを加える
bitset<50> add(bitset<50> S, int x)
{
 S.set(x, 1); // xビット目を1にする
 return S;
}

// 集合Sの内容を昇順で出力する(スペース区切りで各要素の値を出力する)
void print_set(bitset<50> S)
{
 vector<int> cont;
 for (int i = 0; i < 50; i++)
 {
   if (S.test(i))
   {
     cont.push_back(i);
   }
 }
 for (int i = 0; i < cont.size(); i++)
 {
   if (i > 0)
     cout << " ";
   cout << cont.at(i);
 }
 cout << endl;
}

// これより下は書き換えない

int main()
{
 bitset<50> A, B;
 int N;
 cin >> N;
 for (int i = 0; i < N; i++)
 {
   int x;
   cin >> x;
   A = add(A, x);
 }
 int M;
 cin >> M;
 for (int i = 0; i < M; i++)
 {
   int x;
   cin >> x;
   B = add(B, x);
 }

 // 操作
 string com;
 cin >> com;

 if (com == "intersection")
 {
   print_set(intersection(A, B));
 }
 else if (com == "union_set")
 {
   print_set(union_set(A, B));
 }
 else if (com == "symmetric_diff")
 {
   print_set(symmetric_diff(A, B));
 }
 else if (com == "subtract")
 {
   int x;
   cin >> x;
   print_set(subtract(A, x));
 }
 else if (com == "increment")
 {
   print_set(increment(A));
 }
 else if (com == "decrement")
 {
   print_set(decrement(A));
 }
}

これを提出。

大学の講義における効率厨の圧倒的優位性について

僕は大学の講義でよっぽどのことがない限り、ノートをSurfaceで取っていた。
よっぽどのことというのは、頭の固い教授が未だに電子機器の使用を禁止している講義や、手書きノートの提出が必要なもの、毎回演習問題の提出が必要で、配られる解答用紙の裏にノートを取っておいたほうが効率の良い場合、といったもの。
こういった講義は"よっぽど"と記したとおり期間中に1つか2つだけで少なかったが、手書きよりタイピングのほうが早いのは自明なので、非常に煩わしく感じていた。

僕は一応理系学生だが、ノートをPCで取っている生徒は他にはいなかった。
iPad+penでノートを取っている人もいたが、結局は手書きなので、僕にとって魅力には感じなかった。
ちなみに僕も講義でiPadを持ち込んでいたが、教科書を自炊して入れておいたものを講義中に見る、マーカーを入れる程度にしか使っていなかったので、基本置物だった。

理系がノートをPCで取るのは、数式や図形があるため、効率が悪いと思われがちなのだが、OneNoteには手書きで書いた数式を文書に変換してくれる機能があったり、手書き図形をきれいにしてくれる機能があったりするため、実はそこらへんの問題は解決されている。手書きができずTouch Barを自慢してくるMac民は半泣きだろう。
むしろ図形などは補正がかかるため、紙のノートに書くより早かったりする。
理系のノートも説明の大半に日本語を使用するため、タイピングができる人は手書きもできるPCのほうが早いのだ。

僕の周りにはタイピングがフリック入力の速度を上回ることを信じられないとのたまう変人しかいなかったので、結局皆手書きノートを使っていたが、検索機能もなく、いざというときの録音を行っているSurface民以上に効率良く講義を受けている理系大学生はいないと思っている。
文系であれば、講義に数式が出てくる機会も少ないため、むしろPCを使わないなど愚の骨頂であるといえるだろう。

ではなぜ未だにPCを講義に持ち込むスタイルが浸透していないのか。
iPadを教科書代わりにしている人ですら好奇の目で見られていたのだ。
僕なんて完全に変人だっただろう。

嘆かわしいことに、スマートフォンの普及により大半のことはスマホでできると豪語する変人のせいで、大学生のPCを利用する機会は非常に減っていると感じる。
たしかにそのとおり、スマートフォンの進化は目まぐるしく、wordやexcelは編集もできてしまう。
しかし、こんな小さい画面で、入力速度がありえないくらい遅い端末で、効率が悪いと思うことはないのか。

時代は確かに進歩し、技術は我々の生活を豊かにしていく。
しかしながら、技能がある程度必要ながら圧倒的に優れた技術を使わず、制限されたデバイスに姿には、憐憫の情すら湧いてくるのだ。
PCを使いこなす人であれば、スマホができることの限界というものも理解できるはずだ。

確かに、研究によれば、タイピングで入力したものと紙に記したものとで比較すると、紙で入力したもののほうが頭に残るのだという。
僕から言わせてもらえばそれは、予習復習を行わないウェイ族の拠り所にしかなっていない。
講義というものは知識の確認と穴埋めであり、ノートはそれをあとから見返して増強するものだと考えている。
基本勉強というものは自分の力で行われるべきものであり、より専門的な先人が独学でたどり着くことが困難な部分を説明で補ってくれるべきが、大学という研究･教育機関のあるべき姿なのではないだろうか。
そういった点で言えば、教科書の朗読会しかしてくれない教授の講義というものは聴くに値しない。
幾度、講義を聴講したことを後悔したかなど、数え切れるものではない。

結局は、無知は罪なのであり、効率の悪いものは悪なのである。
世の陰キャ共よ、我が同胞よ。
ウェイ族に効率まで負けてはいけないのだ。