[SWEA] 17. ビット演算

2365 ワード
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ビット

  • コンピュータでビット表示データを使用します.
  • 1 bit=0または
  • 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,13,28}で、Bの友達リストは{0,1,4,5,6,17,21,28}です.
  • では、次の問題を解決します.
  • AあるいはBは何人の友达を知っていますか?
  • AとBの間に重なる友達の数は?
  • の繰り返し文を使用して問題を解決できますが、ビットを使用すると、これらの集合演算を簡略化できます.
    • もしx番目の人が私の友达で、
  • の友达のリストを人号に保存するのではなく、x番目の人を1に変換しようとします.
  • のようにAの友達リストは32人になり、32ビットのバイナリ数のうち、0、3、6、7ビットが1で示す0001、000000000010、0100、1100、10012となっている.
  • Bの友達も0001000001000000100112に変えることができます.
  • このように友達リストをビットで保存することで、前の2つの問題を迅速に解決することができます.
    • 第
  • 1)問題は2人の友達のリスト|演算を求めることができる;第2)問題は&演算を求めることができる.
    • [SWEA] 21. 分割征服
    [プログラマー]電話番号リスト