ビット演算

programming

少ししか使いこなせてないから勉強する．

基本演算

  • AND &
  • OR |
  • XOR ^
  • NOT ~
  • 左シフト <<
  • 右シフト（左端はその時の最上位ビットと同じ符号で埋める） >>
  • 右シフト（左端は0で埋める） >>>

小技

  • xを2^n倍する
x << n
  • 右からnビットを立てる(00001111)
(1 << n) - 1;
  • 右からkビット目は立っているか
(x & (1<<k)) > 0;
  • 立っている一番右側のビットだけ残して0にする(00101100->00000100)
x & -x;
  • 立っているビットのうち最下位をクリアする(00101100->00101000)
x & (x-1);
  • next combination

ちょうどkビット立っているような数を入れると次のちょうどkビット立っている組み合わせが出てくる．

long nextCombination(long x){
    long smallest = x & -x;
    long ripple = x+ smallest;
    long _smallest = ripple & -ripple;
    long ones = ((_smallest/smallest)>>1)-1;
    return ripple | ones;
}