Bit演算（bitwise operation）

データをビット列（2進数の0と1の羅列）とみなして、ビットの移動やビット単位の論理演算

演算の種類

AND演算

var a = 45;    // 101101
var b = 25;    // 011001
var c = a & b; // 001001 = 9

OR演算

var a = 45;    // 101101
var b = 25;    // 011001
var c = a | b; // 111101 = 61

ビットシフト演算

各ビットを左または右へシフトする。

左へシフト

var a = 10;     // 01010
var l = a << 1; // 10100 = 20

右へシフト

var a = 10;     // 01010
var r = a >> 1; // 00101 = 5

ビットシフト演算を用いたフラグ管理

n番目のフラグは(1 << n)と表せる。

フラグが立っているかどうか

n番目が立っているかどうかは、ビットシフト演算とAND演算を使用して確認することができる。

var a = 10; // 01010
var result = a & (1 << n);

aのn番目のフラグが立っている場合のみresultは0より大きくなる。

フラグを立てる

n番目のフラグを立てるためには、ビットシフト演算とOR演算を使用することで可能。

var a = 10; // 01010
var b = a | (1 << n);

フラグを消す

n番目のフラグを消すためには、0をAND演算すればよい。

var a = 10; // 01010;
var b = a & ~(1 << n);

代表的な問題

部分集合

{x, y, z}の部分集合は各桁を"選ぶ"・"選ばない"で決まるため2³（8）個存在する。
"選ぶ"がフラグが立っている状態とすると以下のようになる。
000, 001, 010, 011, 100, 101, 110, 111

部分集合のフラグの生成

var setElements = new List<int>(){1, 2, 3};
var elementNumber = setElements.Count;
for (var bit = 0; bit < 1 << elementNumber; ++bit)
  System.Console.WriteLine(System.Convert.ToString(bit, 2).PadLeft(elementNumber, '0'));

部分集合の生成

たとえば101の3桁目はzを、1桁目はxを選んでいることを表している。
n桁目を選んでいるかはフラグが立っているかどうかなので

for (var i = 0; i < elementNumber; ++i)
  if((bit & 1 << i) > 0)

例題

C - Many Formulas

数字からなる文字列が与えられる。
各数字の間に＋を"入れる"or"入れない"の全てのパターンの和を求める。
s "123"⇒{1, 2, 3}, {12, 3}, {1, 23}, {123
"各数字の間に+を入れる"がビットが立っているとする。<br/?>

public static long GetAllEquationSumByBitFullSearch(string s)
  var gap = s.Length - 1;
  
  var ret = new List<long>();
  for (var bit = 0; bit < 1 << gap; ++bit)
  {
    var leftMove = 0;
    long sum = 0;
    for (var rightMove = 0; rightMove < gap; ++rightMove)
    {
      if ((bit & 1 << rightMove) == 0) continue;
      sum += long.Parse(s.Substring(leftMove, rightMove - leftMove + 1));
      leftMove = rightMove + 1;
    }
    sum += long.Parse(s.Substring(leftMove));
    ret.Add(sum);
  }
  return ret.Sum();