ビット演算
少ししか使いこなせてないから勉強する.
基本演算
- 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; }