Search on the blog

2011年8月5日金曜日

ビットを操るgccビルトイン関数たち

gccのビルトイン関数の中で、ビットに関するもののまとめ。

functionfeature
__builtin_clz(unsigned int)count leading zeros
__builtin_ctz(unsigned int)count trailing zeros
__builtin_ffs(unsigned int)find first set bit (1-based)
__builtin_popcount(unsigned int)population count
__builtin_parity(unsigned int)parity of bits set


■使い方とか
1. _builtin_clz(x)は、xを二進数にしたときの頭の0の数を返します。
10は、2進数だと、
00000000000000000000000000001010
なので、28が返ってきます。
ぱっと思いつく応用は、2^i <= x < 2^{i+1}となるiを求めるとか。

2. __builtin_ctz(x)は、xを二進数にしたときのお尻の0の数を返します。
00000000000000000000000000001010
なので、10の場合は、1です。
これを使うと、一発で、lsbの位置(o-based)が分かります。ただし、lsbを使いたい場合は、1<< lsbという使い方が多いと思うので、そういう場合は、x & -xの方がやすい。
xは、2で何回割り切れる?かを調べたいとき、これを使えば一発。

3. __builtin_ffs(x)は、lsbの位置を1-basedの数字で返します。
__builtin_ffs(x) = 1 + __builtin_ctz(x)
の関係がなりたちます。特にこれと言って便利なシチュエーションは浮かびません。すいません。

4. __builtin_popcount(x)は、1が立っているビット数を返します。
10の場合は、2が返ってきます。この関数はビットで集合を表す場合に、重宝します。

5. __builtin_parity(x)は、1が立ってるビットのパリティなので、以下の関係が成り立ちます。
__builtin_parity(unsigned int) = __builtin_popcount(x) % 2
これは、包除原理の足すか引くかの判定のときに、使えます。




0 件のコメント:

コメントを投稿