ビット演算、２進法での取り扱い, bool

C++では、２進法を取り扱うのに文法は特にない。

1000100なら、２みたいに個数をカウントする。

while(n) {
  n = n & n-1;  //n = 10010 &10001
//0になるときは、たとえば、n=10000のとき。 n = 10000 & 01111;
}
結構定番みたい。

n = n >> 1; //10010->01001
int bin = n & 1; //01001 & 00001 bin = 1;

while(x) {
  int bin = x % 2;
  x /= 2;

ARMというアセンブラで、__builtin_??を使ってビットの個数を得ることができる。

//__builtin_popcount
//この組み込み関数は、指定された値の入力カウント、つまり値の 1 ビット数を返します。
__builtin_popcount(n); //n = 3 = 011  ->2

&とか、|とかの優先順位は低いので、必ず括弧をつける癖を付けた方がいい．
//if(n&1 == 0)  //(n&(1 == 0) )と解釈されてしまうので、違う意味になる．
if( (n&1) == 0) //必ず括弧を付けよう．
ちなみに、
if(n%2 == 0)は何の問題もない．
優先順位としては、


%
13


==
9


&
8


^
7


|
6

偶数か奇数かをビットで調べる

if(x&1) {
...
}

二つの数のうち、偶数と奇数が一つずつある時に処理する

if((x^y) & 1 == 0) {  //式の中身が0なら、両方偶数または奇数である。
..
}

数字から、２進法での数字にアクセス。

int n = (int)log2(N);

二進数で右から数えてk桁目が1であるかどうかを調べる

if(n & (1 << k))

//これを応用して、二進数ですでにk桁あると分かっているときk桁目が1であるかどうかを調べたいときとかに使える。

100100 --> 100のように、最大のビット数を取り除きたいとき

n = n & ((1 << (k-1))-1);
k = 6, n = 100110 のとき、n = 100110 & 011111で n=000110となる。

部分和問題を深さ検索を用いず、ビット計算で行う。nがあまり大きくない時に(<30)（だいたい億単位）有効。
計算量を考えれば、25くらいが限界かと。
全探索をするばあいも。

for(int i = 1; i < (1<< n); i++) {
  for(int j = 0; j < n; j++) {
    if(i & (1 << j)) { //masked  e.g)(0110 & 0100) == 0100 != 0
      sum = v[j];
    }
    if(sum == seek) {
      return true;
    }
  }
}

true, falseを文字としてそのまま出力したいときはboolalphaを用いる．マニピュレータ。要するに、endlとかの仲間．

ios_base& boolalpha ( ios_base& str ); //iostream

使い方

boolalpha(cout);
//http://www.cplusplus.com/reference/iostream/manipulators/  参照
cout << isprime[i] << endl;  //これでもきちんと出力される．

cout << boolalpha << isprime[i] << endl;  //これでもOK!こちらの方が使いやすそう．

ostringstream oss;
oss << boolalpha << isprime[i];
cout << oss.str() << endl;  //これでもOK!

//出力をすべて大文字にする．
//気をつけたいことは、int toupper( int c );
//string str; 
//str.c_str()としてもconst型なので、値が書き換えられないことに注意．
ostringstream oss;
oss << boolalpha << isprime[i];  //isprime[i]はbool型
int sz = oss.str().size();  //こういう書き方でも問題ないよ．
string boolstr =  oss.str();
for(int j = 0; j < sz; j++) {
  boolstr[j] = toupper(boolstr[j]);
}
cout <

ビットの全探索

//順番が絡む。
  long long countOrderings(vector  req) {
    int sz = req.size(); //sz <= 31
    map work;
    work[0] = 1;
    for(int i = 0; i < (1<; i++) {
      for(int j = 0; j < sz; j++) {
        if( (i&(1<) {
          for(int k = 0; k < sz; k++) {
           //req[j][k]について適当に処理
          }
        }
      }
    }
  }
/*ビット列は
//0:まだ配置していない
//1:配置された
を表す。*/
//001001 -->0番目と3番目が配置された