競プロで頻出の初歩的な（？）テクニック

使い所は多いけれど説明・紹介されることはあまりないようなテクニックのメモ

自然数A,Bで除算をするとき、大半の言語では切り捨てられることを利用するテク

ex) 切り捨て A/B

切り上げ (A+B-1) / B

1 << n は1をn回左シフトした数を表す、つまり2^nと等しい

また、x & (1 << n)とすることによってxの（下から数えて)nビット目が立っているかどうかを調べることもできる

x & -xはxの一番下に立っているビットを表す（なぜそうなるのかは2の補数でｇｇってください）

よって x / (x & -x)とするとxを2で割れるだけ割った数が得られる

最後に続いている0の数。NLZ(x) = count_bits( (x & (-x) )-1)

最初に続いている0の数。NTZ(x) = 32 - NLZ( (~x) & (x-1) )

C,C++では文字コードはASCIIを使っているので1byte変数として扱うこともできる

この文字コードでなくても(文字が連続しているならば)基本的に演算はできる

例えば

int cnt[26];

cnt[c - 'a']++;//cは小文字のアルファベット

のようにすればa,b,c...に0,1,2...を対応させてそれぞれの文字に対して数え上げなどができる

西瓜の備忘録