[SWEA] 17. ᄑᄑᄑᄑᄑᄑᄑᄑᄑ

2134 ワード
bitwise operation テキストリンク
要素nサブセット→1<<2^nを→>>nで割る
2^nを余剰(パリティ判別)→&nで割る
Swap →
a ^= b;
b ^= a;
a ^= b;
1. 基礎科目
1.1ソフトウェアのトラブルシューティング能力
なぜVIXETAの代わりにVIXOを使うのですか?
  • ビセタはすべての入力に満足していません.
  • は主に限られた時間内の結果、すなわち性能が最も悪い
    • に注目する.
    効率的なアルゴリズムはスーパーコンピュータよりも価値があります!
    2.2標準I/O
    C++I/O
  • cin:標準入力(キーボード)
  • cout:標準出力(画面出力)
  • int width(int w):最小フィールド幅
    • を指定
  • int精密度(int p):有効桁数
    • を設定
  • ファイルの内容を標準入力として読み込みます.
  • freopen(”sample_input.txt”, “r”, stdin);
    • ビット演算
  • 1 << n
    値は
  • 2^nです.
  • は、n個の要素の全ての部分集合の数を表す.
  • 電源セット(すべての部品セット)
  • 共重合
    • 、自己を含む全部分重合.
  • 各要素が2つの場合の数を含むか含まないかは、すべての部分集合の数を計算します.
  • i & ( 1 << j )
  • の計算結果は、iのjビットが1であるか否かを意味する.
  • Bitを使用したサブセットの作成
  • 元素数に相当するN個のビットを利用する.
  • n番目のビット値が1の場合、n番目の要素が含まれていることを示します.
    • ミスの表現←近似の表現
    整数をバイナリで表すのは問題ありませんが、エラーを表すには十分ではありません.→誤差が累積する可能性がある
    1.ビット演算
    2.1 ビット
  • コンピュータでビット表示データを使用します.
  • 1bit = 0 または1
  • 8bit = 1byte
    • 2.3 除算
    一般的な/および%演算子はオーバーヘッドが大きいため、必要に応じてより速いビット演算を使用できます.
    2.3.1 分割ぶんかつ
    数で割る 2^n 境遇 >> 演算子は、/演算子を置換できます.
    ex) 9/8 = 9/ 2^3 = 1 -> 10012 >> 3 = 12
    2.3.2残り

  • 数で割る 2^n もしそうであれば、%演算子の代わりに演算子を使用できます.

  • 2^n バイナリで表すと、トップビットのみが1の形状で表示されます. 2^nで–1 さらにn-1回以下のBitを全て1にすればよい.
    ex) 9 % 4 = 1 -> 10012 & 112 = 12

  • 奇数判別にも適用できる
    ex) n % 2 = n & 1
    • 2.4 SWAP
    XOR 演算により、一時変数を宣言せずに2つの変数の値を変更できます.
    int a, b;
a = 10, b = 30;
a ^= b;
b ^= a;
a ^= b;
    2.5 ビットマスク
    1つのFlagとして
  • Bitを使用すると、データの格納と集合表現を簡略化できます.
  • 人の番号は0から31で、Aの友達リストは{0、3、6、7、10、13、28}で、Bの友達リストは {0,1,4,5,6,17,21,21,28}.
  • では、次の問題を解決します.
  • A それともBが知っている友達は?
  • AとBの間に重なる友達の数は?
  • の繰り返し文を使用して問題を解決できますが、ビットを使用すると、これらの集合演算を簡略化できます.
    • もしx番目の人が私の友达で、
  • の友达のリストを人号に保存するのではなく、x番目の人を1に変換しようとします.
  • ならAの友達リストは32人なので32桁のバイナリ数のうち、0、3、6、7桁が1の0001億000010、0100、10012 .
  • Bの友達もこのように変えることができます:0001 0000100 000011 00112 .
  • このように友達リストをビットで保存することで、前の2つの問題を迅速に解決することができます.
    • 第
  • 1)問題は2人の友達のリスト|演算を求めることができる;第2)問題は&演算を求めることができる.
    • Android:「ボタンButton設定文字Stringアルファベットを含む場合、アルファベットが自動的に大文字文字列になる」という問題を解決
    を構築するミニGoogleドライブクローンを迅速に